omap2+: add drm device
[pandora-kernel.git] / mm / page_alloc.c
1 /*
2  *  linux/mm/page_alloc.c
3  *
4  *  Manages the free list, the system allocates free pages here.
5  *  Note that kmalloc() lives in slab.c
6  *
7  *  Copyright (C) 1991, 1992, 1993, 1994  Linus Torvalds
8  *  Swap reorganised 29.12.95, Stephen Tweedie
9  *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
10  *  Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999
11  *  Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
12  *  Zone balancing, Kanoj Sarcar, SGI, Jan 2000
13  *  Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002
14  *          (lots of bits borrowed from Ingo Molnar & Andrew Morton)
15  */
16
17 #include <linux/stddef.h>
18 #include <linux/mm.h>
19 #include <linux/swap.h>
20 #include <linux/interrupt.h>
21 #include <linux/pagemap.h>
22 #include <linux/jiffies.h>
23 #include <linux/bootmem.h>
24 #include <linux/memblock.h>
25 #include <linux/compiler.h>
26 #include <linux/kernel.h>
27 #include <linux/kmemcheck.h>
28 #include <linux/module.h>
29 #include <linux/suspend.h>
30 #include <linux/pagevec.h>
31 #include <linux/blkdev.h>
32 #include <linux/slab.h>
33 #include <linux/ratelimit.h>
34 #include <linux/oom.h>
35 #include <linux/notifier.h>
36 #include <linux/topology.h>
37 #include <linux/sysctl.h>
38 #include <linux/cpu.h>
39 #include <linux/cpuset.h>
40 #include <linux/memory_hotplug.h>
41 #include <linux/nodemask.h>
42 #include <linux/vmalloc.h>
43 #include <linux/vmstat.h>
44 #include <linux/mempolicy.h>
45 #include <linux/stop_machine.h>
46 #include <linux/sort.h>
47 #include <linux/pfn.h>
48 #include <linux/backing-dev.h>
49 #include <linux/fault-inject.h>
50 #include <linux/page-isolation.h>
51 #include <linux/page_cgroup.h>
52 #include <linux/debugobjects.h>
53 #include <linux/kmemleak.h>
54 #include <linux/memory.h>
55 #include <linux/compaction.h>
56 #include <trace/events/kmem.h>
57 #include <linux/ftrace_event.h>
58 #include <linux/memcontrol.h>
59 #include <linux/prefetch.h>
60 #include <linux/migrate.h>
61 #include <linux/page-debug-flags.h>
62
63 #include <asm/tlbflush.h>
64 #include <asm/div64.h>
65 #include "internal.h"
66
67 #ifdef CONFIG_USE_PERCPU_NUMA_NODE_ID
68 DEFINE_PER_CPU(int, numa_node);
69 EXPORT_PER_CPU_SYMBOL(numa_node);
70 #endif
71
72 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
73 /*
74  * N.B., Do NOT reference the '_numa_mem_' per cpu variable directly.
75  * It will not be defined when CONFIG_HAVE_MEMORYLESS_NODES is not defined.
76  * Use the accessor functions set_numa_mem(), numa_mem_id() and cpu_to_mem()
77  * defined in <linux/topology.h>.
78  */
79 DEFINE_PER_CPU(int, _numa_mem_);                /* Kernel "local memory" node */
80 EXPORT_PER_CPU_SYMBOL(_numa_mem_);
81 #endif
82
83 /*
84  * Array of node states.
85  */
86 nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
87         [N_POSSIBLE] = NODE_MASK_ALL,
88         [N_ONLINE] = { { [0] = 1UL } },
89 #ifndef CONFIG_NUMA
90         [N_NORMAL_MEMORY] = { { [0] = 1UL } },
91 #ifdef CONFIG_HIGHMEM
92         [N_HIGH_MEMORY] = { { [0] = 1UL } },
93 #endif
94         [N_CPU] = { { [0] = 1UL } },
95 #endif  /* NUMA */
96 };
97 EXPORT_SYMBOL(node_states);
98
99 unsigned long totalram_pages __read_mostly;
100 unsigned long totalreserve_pages __read_mostly;
101 /*
102  * When calculating the number of globally allowed dirty pages, there
103  * is a certain number of per-zone reserves that should not be
104  * considered dirtyable memory.  This is the sum of those reserves
105  * over all existing zones that contribute dirtyable memory.
106  */
107 unsigned long dirty_balance_reserve __read_mostly;
108
109 int percpu_pagelist_fraction;
110 gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
111
112 #ifdef CONFIG_PM_SLEEP
113 /*
114  * The following functions are used by the suspend/hibernate code to temporarily
115  * change gfp_allowed_mask in order to avoid using I/O during memory allocations
116  * while devices are suspended.  To avoid races with the suspend/hibernate code,
117  * they should always be called with pm_mutex held (gfp_allowed_mask also should
118  * only be modified with pm_mutex held, unless the suspend/hibernate code is
119  * guaranteed not to run in parallel with that modification).
120  */
121
122 static gfp_t saved_gfp_mask;
123
124 void pm_restore_gfp_mask(void)
125 {
126         WARN_ON(!mutex_is_locked(&pm_mutex));
127         if (saved_gfp_mask) {
128                 gfp_allowed_mask = saved_gfp_mask;
129                 saved_gfp_mask = 0;
130         }
131 }
132
133 void pm_restrict_gfp_mask(void)
134 {
135         WARN_ON(!mutex_is_locked(&pm_mutex));
136         WARN_ON(saved_gfp_mask);
137         saved_gfp_mask = gfp_allowed_mask;
138         gfp_allowed_mask &= ~GFP_IOFS;
139 }
140
141 bool pm_suspended_storage(void)
142 {
143         if ((gfp_allowed_mask & GFP_IOFS) == GFP_IOFS)
144                 return false;
145         return true;
146 }
147 #endif /* CONFIG_PM_SLEEP */
148
149 #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
150 int pageblock_order __read_mostly;
151 #endif
152
153 static void __free_pages_ok(struct page *page, unsigned int order);
154
155 /*
156  * results with 256, 32 in the lowmem_reserve sysctl:
157  *      1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
158  *      1G machine -> (16M dma, 784M normal, 224M high)
159  *      NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
160  *      HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
161  *      HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
162  *
163  * TBD: should special case ZONE_DMA32 machines here - in those we normally
164  * don't need any ZONE_NORMAL reservation
165  */
166 int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
167 #ifdef CONFIG_ZONE_DMA
168          256,
169 #endif
170 #ifdef CONFIG_ZONE_DMA32
171          256,
172 #endif
173 #ifdef CONFIG_HIGHMEM
174          32,
175 #endif
176          32,
177 };
178
179 EXPORT_SYMBOL(totalram_pages);
180
181 static char * const zone_names[MAX_NR_ZONES] = {
182 #ifdef CONFIG_ZONE_DMA
183          "DMA",
184 #endif
185 #ifdef CONFIG_ZONE_DMA32
186          "DMA32",
187 #endif
188          "Normal",
189 #ifdef CONFIG_HIGHMEM
190          "HighMem",
191 #endif
192          "Movable",
193 };
194
195 int min_free_kbytes = 1024;
196
197 static unsigned long __meminitdata nr_kernel_pages;
198 static unsigned long __meminitdata nr_all_pages;
199 static unsigned long __meminitdata dma_reserve;
200
201 #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
202   /*
203    * MAX_ACTIVE_REGIONS determines the maximum number of distinct
204    * ranges of memory (RAM) that may be registered with add_active_range().
205    * Ranges passed to add_active_range() will be merged if possible
206    * so the number of times add_active_range() can be called is
207    * related to the number of nodes and the number of holes
208    */
209   #ifdef CONFIG_MAX_ACTIVE_REGIONS
210     /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */
211     #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS
212   #else
213     #if MAX_NUMNODES >= 32
214       /* If there can be many nodes, allow up to 50 holes per node */
215       #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50)
216     #else
217       /* By default, allow up to 256 distinct regions */
218       #define MAX_ACTIVE_REGIONS 256
219     #endif
220   #endif
221
222   static struct node_active_region __meminitdata early_node_map[MAX_ACTIVE_REGIONS];
223   static int __meminitdata nr_nodemap_entries;
224   static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
225   static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
226   static unsigned long __initdata required_kernelcore;
227   static unsigned long __initdata required_movablecore;
228   static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
229
230   /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
231   int movable_zone;
232   EXPORT_SYMBOL(movable_zone);
233 #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
234
235 #if MAX_NUMNODES > 1
236 int nr_node_ids __read_mostly = MAX_NUMNODES;
237 int nr_online_nodes __read_mostly = 1;
238 EXPORT_SYMBOL(nr_node_ids);
239 EXPORT_SYMBOL(nr_online_nodes);
240 #endif
241
242 int page_group_by_mobility_disabled __read_mostly;
243
244 static void set_pageblock_migratetype(struct page *page, int migratetype)
245 {
246
247         if (unlikely(page_group_by_mobility_disabled))
248                 migratetype = MIGRATE_UNMOVABLE;
249
250         set_pageblock_flags_group(page, (unsigned long)migratetype,
251                                         PB_migrate, PB_migrate_end);
252 }
253
254 bool oom_killer_disabled __read_mostly;
255
256 #ifdef CONFIG_DEBUG_VM
257 static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
258 {
259         int ret = 0;
260         unsigned seq;
261         unsigned long pfn = page_to_pfn(page);
262
263         do {
264                 seq = zone_span_seqbegin(zone);
265                 if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
266                         ret = 1;
267                 else if (pfn < zone->zone_start_pfn)
268                         ret = 1;
269         } while (zone_span_seqretry(zone, seq));
270
271         return ret;
272 }
273
274 static int page_is_consistent(struct zone *zone, struct page *page)
275 {
276         if (!pfn_valid_within(page_to_pfn(page)))
277                 return 0;
278         if (zone != page_zone(page))
279                 return 0;
280
281         return 1;
282 }
283 /*
284  * Temporary debugging check for pages not lying within a given zone.
285  */
286 static int bad_range(struct zone *zone, struct page *page)
287 {
288         if (page_outside_zone_boundaries(zone, page))
289                 return 1;
290         if (!page_is_consistent(zone, page))
291                 return 1;
292
293         return 0;
294 }
295 #else
296 static inline int bad_range(struct zone *zone, struct page *page)
297 {
298         return 0;
299 }
300 #endif
301
302 static void bad_page(struct page *page)
303 {
304         static unsigned long resume;
305         static unsigned long nr_shown;
306         static unsigned long nr_unshown;
307
308         /* Don't complain about poisoned pages */
309         if (PageHWPoison(page)) {
310                 reset_page_mapcount(page); /* remove PageBuddy */
311                 return;
312         }
313
314         /*
315          * Allow a burst of 60 reports, then keep quiet for that minute;
316          * or allow a steady drip of one report per second.
317          */
318         if (nr_shown == 60) {
319                 if (time_before(jiffies, resume)) {
320                         nr_unshown++;
321                         goto out;
322                 }
323                 if (nr_unshown) {
324                         printk(KERN_ALERT
325                               "BUG: Bad page state: %lu messages suppressed\n",
326                                 nr_unshown);
327                         nr_unshown = 0;
328                 }
329                 nr_shown = 0;
330         }
331         if (nr_shown++ == 0)
332                 resume = jiffies + 60 * HZ;
333
334         printk(KERN_ALERT "BUG: Bad page state in process %s  pfn:%05lx\n",
335                 current->comm, page_to_pfn(page));
336         dump_page(page);
337
338         print_modules();
339         dump_stack();
340 out:
341         /* Leave bad fields for debug, except PageBuddy could make trouble */
342         reset_page_mapcount(page); /* remove PageBuddy */
343         add_taint(TAINT_BAD_PAGE);
344 }
345
346 /*
347  * Higher-order pages are called "compound pages".  They are structured thusly:
348  *
349  * The first PAGE_SIZE page is called the "head page".
350  *
351  * The remaining PAGE_SIZE pages are called "tail pages".
352  *
353  * All pages have PG_compound set.  All pages have their ->private pointing at
354  * the head page (even the head page has this).
355  *
356  * The first tail page's ->lru.next holds the address of the compound page's
357  * put_page() function.  Its ->lru.prev holds the order of allocation.
358  * This usage means that zero-order pages may not be compound.
359  */
360
361 static void free_compound_page(struct page *page)
362 {
363         __free_pages_ok(page, compound_order(page));
364 }
365
366 void prep_compound_page(struct page *page, unsigned long order)
367 {
368         int i;
369         int nr_pages = 1 << order;
370
371         set_compound_page_dtor(page, free_compound_page);
372         set_compound_order(page, order);
373         __SetPageHead(page);
374         for (i = 1; i < nr_pages; i++) {
375                 struct page *p = page + i;
376                 __SetPageTail(p);
377                 set_page_count(p, 0);
378                 p->first_page = page;
379         }
380 }
381
382 /* update __split_huge_page_refcount if you change this function */
383 static int destroy_compound_page(struct page *page, unsigned long order)
384 {
385         int i;
386         int nr_pages = 1 << order;
387         int bad = 0;
388
389         if (unlikely(compound_order(page) != order) ||
390             unlikely(!PageHead(page))) {
391                 bad_page(page);
392                 bad++;
393         }
394
395         __ClearPageHead(page);
396
397         for (i = 1; i < nr_pages; i++) {
398                 struct page *p = page + i;
399
400                 if (unlikely(!PageTail(p) || (p->first_page != page))) {
401                         bad_page(page);
402                         bad++;
403                 }
404                 __ClearPageTail(p);
405         }
406
407         return bad;
408 }
409
410 static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
411 {
412         int i;
413
414         /*
415          * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
416          * and __GFP_HIGHMEM from hard or soft interrupt context.
417          */
418         VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
419         for (i = 0; i < (1 << order); i++)
420                 clear_highpage(page + i);
421 }
422
423 #ifdef CONFIG_DEBUG_PAGEALLOC
424 unsigned int _debug_guardpage_minorder;
425
426 static int __init debug_guardpage_minorder_setup(char *buf)
427 {
428         unsigned long res;
429
430         if (kstrtoul(buf, 10, &res) < 0 ||  res > MAX_ORDER / 2) {
431                 printk(KERN_ERR "Bad debug_guardpage_minorder value\n");
432                 return 0;
433         }
434         _debug_guardpage_minorder = res;
435         printk(KERN_INFO "Setting debug_guardpage_minorder to %lu\n", res);
436         return 0;
437 }
438 __setup("debug_guardpage_minorder=", debug_guardpage_minorder_setup);
439
440 static inline void set_page_guard_flag(struct page *page)
441 {
442         __set_bit(PAGE_DEBUG_FLAG_GUARD, &page->debug_flags);
443 }
444
445 static inline void clear_page_guard_flag(struct page *page)
446 {
447         __clear_bit(PAGE_DEBUG_FLAG_GUARD, &page->debug_flags);
448 }
449 #else
450 static inline void set_page_guard_flag(struct page *page) { }
451 static inline void clear_page_guard_flag(struct page *page) { }
452 #endif
453
454 static inline void set_page_order(struct page *page, int order)
455 {
456         set_page_private(page, order);
457         __SetPageBuddy(page);
458 }
459
460 static inline void rmv_page_order(struct page *page)
461 {
462         __ClearPageBuddy(page);
463         set_page_private(page, 0);
464 }
465
466 /*
467  * Locate the struct page for both the matching buddy in our
468  * pair (buddy1) and the combined O(n+1) page they form (page).
469  *
470  * 1) Any buddy B1 will have an order O twin B2 which satisfies
471  * the following equation:
472  *     B2 = B1 ^ (1 << O)
473  * For example, if the starting buddy (buddy2) is #8 its order
474  * 1 buddy is #10:
475  *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
476  *
477  * 2) Any buddy B will have an order O+1 parent P which
478  * satisfies the following equation:
479  *     P = B & ~(1 << O)
480  *
481  * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
482  */
483 static inline unsigned long
484 __find_buddy_index(unsigned long page_idx, unsigned int order)
485 {
486         return page_idx ^ (1 << order);
487 }
488
489 /*
490  * This function checks whether a page is free && is the buddy
491  * we can do coalesce a page and its buddy if
492  * (a) the buddy is not in a hole &&
493  * (b) the buddy is in the buddy system &&
494  * (c) a page and its buddy have the same order &&
495  * (d) a page and its buddy are in the same zone.
496  *
497  * For recording whether a page is in the buddy system, we set ->_mapcount -2.
498  * Setting, clearing, and testing _mapcount -2 is serialized by zone->lock.
499  *
500  * For recording page's order, we use page_private(page).
501  */
502 static inline int page_is_buddy(struct page *page, struct page *buddy,
503                                                                 int order)
504 {
505         if (!pfn_valid_within(page_to_pfn(buddy)))
506                 return 0;
507
508         if (page_zone_id(page) != page_zone_id(buddy))
509                 return 0;
510
511         if (page_is_guard(buddy) && page_order(buddy) == order) {
512                 VM_BUG_ON(page_count(buddy) != 0);
513                 return 1;
514         }
515
516         if (PageBuddy(buddy) && page_order(buddy) == order) {
517                 VM_BUG_ON(page_count(buddy) != 0);
518                 return 1;
519         }
520         return 0;
521 }
522
523 /*
524  * Freeing function for a buddy system allocator.
525  *
526  * The concept of a buddy system is to maintain direct-mapped table
527  * (containing bit values) for memory blocks of various "orders".
528  * The bottom level table contains the map for the smallest allocatable
529  * units of memory (here, pages), and each level above it describes
530  * pairs of units from the levels below, hence, "buddies".
531  * At a high level, all that happens here is marking the table entry
532  * at the bottom level available, and propagating the changes upward
533  * as necessary, plus some accounting needed to play nicely with other
534  * parts of the VM system.
535  * At each level, we keep a list of pages, which are heads of continuous
536  * free pages of length of (1 << order) and marked with _mapcount -2. Page's
537  * order is recorded in page_private(page) field.
538  * So when we are allocating or freeing one, we can derive the state of the
539  * other.  That is, if we allocate a small block, and both were
540  * free, the remainder of the region must be split into blocks.
541  * If a block is freed, and its buddy is also free, then this
542  * triggers coalescing into a block of larger size.
543  *
544  * -- wli
545  */
546
547 static inline void __free_one_page(struct page *page,
548                 struct zone *zone, unsigned int order,
549                 int migratetype)
550 {
551         unsigned long page_idx;
552         unsigned long combined_idx;
553         unsigned long uninitialized_var(buddy_idx);
554         struct page *buddy;
555
556         if (unlikely(PageCompound(page)))
557                 if (unlikely(destroy_compound_page(page, order)))
558                         return;
559
560         VM_BUG_ON(migratetype == -1);
561
562         page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
563
564         VM_BUG_ON(page_idx & ((1 << order) - 1));
565         VM_BUG_ON(bad_range(zone, page));
566
567         while (order < MAX_ORDER-1) {
568                 buddy_idx = __find_buddy_index(page_idx, order);
569                 buddy = page + (buddy_idx - page_idx);
570                 if (!page_is_buddy(page, buddy, order))
571                         break;
572                 /*
573                  * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
574                  * merge with it and move up one order.
575                  */
576                 if (page_is_guard(buddy)) {
577                         clear_page_guard_flag(buddy);
578                         set_page_private(page, 0);
579                         __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
580                 } else {
581                         list_del(&buddy->lru);
582                         zone->free_area[order].nr_free--;
583                         rmv_page_order(buddy);
584                 }
585                 combined_idx = buddy_idx & page_idx;
586                 page = page + (combined_idx - page_idx);
587                 page_idx = combined_idx;
588                 order++;
589         }
590         set_page_order(page, order);
591
592         /*
593          * If this is not the largest possible page, check if the buddy
594          * of the next-highest order is free. If it is, it's possible
595          * that pages are being freed that will coalesce soon. In case,
596          * that is happening, add the free page to the tail of the list
597          * so it's less likely to be used soon and more likely to be merged
598          * as a higher order page
599          */
600         if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
601                 struct page *higher_page, *higher_buddy;
602                 combined_idx = buddy_idx & page_idx;
603                 higher_page = page + (combined_idx - page_idx);
604                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
605                 higher_buddy = higher_page + (buddy_idx - combined_idx);
606                 if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
607                         list_add_tail(&page->lru,
608                                 &zone->free_area[order].free_list[migratetype]);
609                         goto out;
610                 }
611         }
612
613         list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
614 out:
615         zone->free_area[order].nr_free++;
616 }
617
618 /*
619  * free_page_mlock() -- clean up attempts to free and mlocked() page.
620  * Page should not be on lru, so no need to fix that up.
621  * free_pages_check() will verify...
622  */
623 static inline void free_page_mlock(struct page *page)
624 {
625         __dec_zone_page_state(page, NR_MLOCK);
626         __count_vm_event(UNEVICTABLE_MLOCKFREED);
627 }
628
629 static inline int free_pages_check(struct page *page)
630 {
631         if (unlikely(page_mapcount(page) |
632                 (page->mapping != NULL)  |
633                 (atomic_read(&page->_count) != 0) |
634                 (page->flags & PAGE_FLAGS_CHECK_AT_FREE) |
635                 (mem_cgroup_bad_page_check(page)))) {
636                 bad_page(page);
637                 return 1;
638         }
639         if (page->flags & PAGE_FLAGS_CHECK_AT_PREP)
640                 page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
641         return 0;
642 }
643
644 /*
645  * Frees a number of pages from the PCP lists
646  * Assumes all pages on list are in same zone, and of same order.
647  * count is the number of pages to free.
648  *
649  * If the zone was previously in an "all pages pinned" state then look to
650  * see if this freeing clears that state.
651  *
652  * And clear the zone's pages_scanned counter, to hold off the "all pages are
653  * pinned" detection logic.
654  */
655 static void free_pcppages_bulk(struct zone *zone, int count,
656                                         struct per_cpu_pages *pcp)
657 {
658         int migratetype = 0;
659         int batch_free = 0;
660         int to_free = count;
661
662         spin_lock(&zone->lock);
663         zone->all_unreclaimable = 0;
664         zone->pages_scanned = 0;
665
666         while (to_free) {
667                 struct page *page;
668                 struct list_head *list;
669
670                 /*
671                  * Remove pages from lists in a round-robin fashion. A
672                  * batch_free count is maintained that is incremented when an
673                  * empty list is encountered.  This is so more pages are freed
674                  * off fuller lists instead of spinning excessively around empty
675                  * lists
676                  */
677                 do {
678                         batch_free++;
679                         if (++migratetype == MIGRATE_PCPTYPES)
680                                 migratetype = 0;
681                         list = &pcp->lists[migratetype];
682                 } while (list_empty(list));
683
684                 /* This is the only non-empty list. Free them all. */
685                 if (batch_free == MIGRATE_PCPTYPES)
686                         batch_free = to_free;
687
688                 do {
689                         page = list_entry(list->prev, struct page, lru);
690                         /* must delete as __free_one_page list manipulates */
691                         list_del(&page->lru);
692                         /* MIGRATE_MOVABLE list may include MIGRATE_RESERVEs */
693                         __free_one_page(page, zone, 0, page_private(page));
694                         trace_mm_page_pcpu_drain(page, 0, page_private(page));
695                 } while (--to_free && --batch_free && !list_empty(list));
696         }
697         __mod_zone_page_state(zone, NR_FREE_PAGES, count);
698         spin_unlock(&zone->lock);
699 }
700
701 static void free_one_page(struct zone *zone, struct page *page, int order,
702                                 int migratetype)
703 {
704         spin_lock(&zone->lock);
705         zone->all_unreclaimable = 0;
706         zone->pages_scanned = 0;
707
708         __free_one_page(page, zone, order, migratetype);
709         __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
710         spin_unlock(&zone->lock);
711 }
712
713 static bool free_pages_prepare(struct page *page, unsigned int order)
714 {
715         int i;
716         int bad = 0;
717
718         trace_mm_page_free(page, order);
719         kmemcheck_free_shadow(page, order);
720
721         if (PageAnon(page))
722                 page->mapping = NULL;
723         for (i = 0; i < (1 << order); i++)
724                 bad += free_pages_check(page + i);
725         if (bad)
726                 return false;
727
728         if (!PageHighMem(page)) {
729                 debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
730                 debug_check_no_obj_freed(page_address(page),
731                                            PAGE_SIZE << order);
732         }
733         arch_free_page(page, order);
734         kernel_map_pages(page, 1 << order, 0);
735
736         return true;
737 }
738
739 static void __free_pages_ok(struct page *page, unsigned int order)
740 {
741         unsigned long flags;
742         int wasMlocked = __TestClearPageMlocked(page);
743
744         if (!free_pages_prepare(page, order))
745                 return;
746
747         local_irq_save(flags);
748         if (unlikely(wasMlocked))
749                 free_page_mlock(page);
750         __count_vm_events(PGFREE, 1 << order);
751         free_one_page(page_zone(page), page, order,
752                                         get_pageblock_migratetype(page));
753         local_irq_restore(flags);
754 }
755
756 /*
757  * permit the bootmem allocator to evade page validation on high-order frees
758  */
759 void __meminit __free_pages_bootmem(struct page *page, unsigned int order)
760 {
761         if (order == 0) {
762                 __ClearPageReserved(page);
763                 set_page_count(page, 0);
764                 set_page_refcounted(page);
765                 __free_page(page);
766         } else {
767                 int loop;
768
769                 prefetchw(page);
770                 for (loop = 0; loop < BITS_PER_LONG; loop++) {
771                         struct page *p = &page[loop];
772
773                         if (loop + 1 < BITS_PER_LONG)
774                                 prefetchw(p + 1);
775                         __ClearPageReserved(p);
776                         set_page_count(p, 0);
777                 }
778
779                 set_page_refcounted(page);
780                 __free_pages(page, order);
781         }
782 }
783
784 #ifdef CONFIG_CMA
785 /* Free whole pageblock and set it's migration type to MIGRATE_CMA. */
786 void __init init_cma_reserved_pageblock(struct page *page)
787 {
788         unsigned i = pageblock_nr_pages;
789         struct page *p = page;
790
791         do {
792                 __ClearPageReserved(p);
793                 set_page_count(p, 0);
794         } while (++p, --i);
795
796         set_page_refcounted(page);
797         set_pageblock_migratetype(page, MIGRATE_CMA);
798         __free_pages(page, pageblock_order);
799         totalram_pages += pageblock_nr_pages;
800 }
801 #endif
802
803 /*
804  * The order of subdivision here is critical for the IO subsystem.
805  * Please do not alter this order without good reasons and regression
806  * testing. Specifically, as large blocks of memory are subdivided,
807  * the order in which smaller blocks are delivered depends on the order
808  * they're subdivided in this function. This is the primary factor
809  * influencing the order in which pages are delivered to the IO
810  * subsystem according to empirical testing, and this is also justified
811  * by considering the behavior of a buddy system containing a single
812  * large block of memory acted on by a series of small allocations.
813  * This behavior is a critical factor in sglist merging's success.
814  *
815  * -- wli
816  */
817 static inline void expand(struct zone *zone, struct page *page,
818         int low, int high, struct free_area *area,
819         int migratetype)
820 {
821         unsigned long size = 1 << high;
822
823         while (high > low) {
824                 area--;
825                 high--;
826                 size >>= 1;
827                 VM_BUG_ON(bad_range(zone, &page[size]));
828
829 #ifdef CONFIG_DEBUG_PAGEALLOC
830                 if (high < debug_guardpage_minorder()) {
831                         /*
832                          * Mark as guard pages (or page), that will allow to
833                          * merge back to allocator when buddy will be freed.
834                          * Corresponding page table entries will not be touched,
835                          * pages will stay not present in virtual address space
836                          */
837                         INIT_LIST_HEAD(&page[size].lru);
838                         set_page_guard_flag(&page[size]);
839                         set_page_private(&page[size], high);
840                         /* Guard pages are not available for any usage */
841                         __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << high));
842                         continue;
843                 }
844 #endif
845                 list_add(&page[size].lru, &area->free_list[migratetype]);
846                 area->nr_free++;
847                 set_page_order(&page[size], high);
848         }
849 }
850
851 /*
852  * This page is about to be returned from the page allocator
853  */
854 static inline int check_new_page(struct page *page)
855 {
856         if (unlikely(page_mapcount(page) |
857                 (page->mapping != NULL)  |
858                 (atomic_read(&page->_count) != 0)  |
859                 (page->flags & PAGE_FLAGS_CHECK_AT_PREP) |
860                 (mem_cgroup_bad_page_check(page)))) {
861                 bad_page(page);
862                 return 1;
863         }
864         return 0;
865 }
866
867 static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
868 {
869         int i;
870
871         for (i = 0; i < (1 << order); i++) {
872                 struct page *p = page + i;
873                 if (unlikely(check_new_page(p)))
874                         return 1;
875         }
876
877         set_page_private(page, 0);
878         set_page_refcounted(page);
879
880         arch_alloc_page(page, order);
881         kernel_map_pages(page, 1 << order, 1);
882
883         if (gfp_flags & __GFP_ZERO)
884                 prep_zero_page(page, order, gfp_flags);
885
886         if (order && (gfp_flags & __GFP_COMP))
887                 prep_compound_page(page, order);
888
889         return 0;
890 }
891
892 /*
893  * Go through the free lists for the given migratetype and remove
894  * the smallest available page from the freelists
895  */
896 static inline
897 struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
898                                                 int migratetype)
899 {
900         unsigned int current_order;
901         struct free_area * area;
902         struct page *page;
903
904         /* Find a page of the appropriate size in the preferred list */
905         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
906                 area = &(zone->free_area[current_order]);
907                 if (list_empty(&area->free_list[migratetype]))
908                         continue;
909
910                 page = list_entry(area->free_list[migratetype].next,
911                                                         struct page, lru);
912                 list_del(&page->lru);
913                 rmv_page_order(page);
914                 area->nr_free--;
915                 expand(zone, page, order, current_order, area, migratetype);
916                 return page;
917         }
918
919         return NULL;
920 }
921
922
923 /*
924  * This array describes the order lists are fallen back to when
925  * the free lists for the desirable migrate type are depleted
926  */
927 static int fallbacks[MIGRATE_TYPES][4] = {
928         [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,     MIGRATE_RESERVE },
929         [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,     MIGRATE_RESERVE },
930 #ifdef CONFIG_CMA
931         [MIGRATE_MOVABLE]     = { MIGRATE_CMA,         MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
932         [MIGRATE_CMA]         = { MIGRATE_RESERVE }, /* Never used */
933 #else
934         [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE,   MIGRATE_RESERVE },
935 #endif
936         [MIGRATE_RESERVE]     = { MIGRATE_RESERVE }, /* Never used */
937         [MIGRATE_ISOLATE]     = { MIGRATE_RESERVE }, /* Never used */
938 };
939
940 /*
941  * Move the free pages in a range to the free lists of the requested type.
942  * Note that start_page and end_pages are not aligned on a pageblock
943  * boundary. If alignment is required, use move_freepages_block()
944  */
945 static int move_freepages(struct zone *zone,
946                           struct page *start_page, struct page *end_page,
947                           int migratetype)
948 {
949         struct page *page;
950         unsigned long order;
951         int pages_moved = 0;
952
953 #ifndef CONFIG_HOLES_IN_ZONE
954         /*
955          * page_zone is not safe to call in this context when
956          * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
957          * anyway as we check zone boundaries in move_freepages_block().
958          * Remove at a later date when no bug reports exist related to
959          * grouping pages by mobility
960          */
961         BUG_ON(page_zone(start_page) != page_zone(end_page));
962 #endif
963
964         for (page = start_page; page <= end_page;) {
965                 /* Make sure we are not inadvertently changing nodes */
966                 VM_BUG_ON(page_to_nid(page) != zone_to_nid(zone));
967
968                 if (!pfn_valid_within(page_to_pfn(page))) {
969                         page++;
970                         continue;
971                 }
972
973                 if (!PageBuddy(page)) {
974                         page++;
975                         continue;
976                 }
977
978                 order = page_order(page);
979                 list_move(&page->lru,
980                           &zone->free_area[order].free_list[migratetype]);
981                 page += 1 << order;
982                 pages_moved += 1 << order;
983         }
984
985         return pages_moved;
986 }
987
988 static int move_freepages_block(struct zone *zone, struct page *page,
989                                 int migratetype)
990 {
991         unsigned long start_pfn, end_pfn;
992         struct page *start_page, *end_page;
993
994         start_pfn = page_to_pfn(page);
995         start_pfn = start_pfn & ~(pageblock_nr_pages-1);
996         start_page = pfn_to_page(start_pfn);
997         end_page = start_page + pageblock_nr_pages - 1;
998         end_pfn = start_pfn + pageblock_nr_pages - 1;
999
1000         /* Do not cross zone boundaries */
1001         if (start_pfn < zone->zone_start_pfn)
1002                 start_page = page;
1003         if (end_pfn >= zone->zone_start_pfn + zone->spanned_pages)
1004                 return 0;
1005
1006         return move_freepages(zone, start_page, end_page, migratetype);
1007 }
1008
1009 static void change_pageblock_range(struct page *pageblock_page,
1010                                         int start_order, int migratetype)
1011 {
1012         int nr_pageblocks = 1 << (start_order - pageblock_order);
1013
1014         while (nr_pageblocks--) {
1015                 set_pageblock_migratetype(pageblock_page, migratetype);
1016                 pageblock_page += pageblock_nr_pages;
1017         }
1018 }
1019
1020 /* Remove an element from the buddy allocator from the fallback list */
1021 static inline struct page *
1022 __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
1023 {
1024         struct free_area * area;
1025         int current_order;
1026         struct page *page;
1027         int migratetype, i;
1028
1029         /* Find the largest possible block of pages in the other list */
1030         for (current_order = MAX_ORDER-1; current_order >= order;
1031                                                 --current_order) {
1032                 for (i = 0;; i++) {
1033                         migratetype = fallbacks[start_migratetype][i];
1034
1035                         /* MIGRATE_RESERVE handled later if necessary */
1036                         if (migratetype == MIGRATE_RESERVE)
1037                                 break;
1038
1039                         area = &(zone->free_area[current_order]);
1040                         if (list_empty(&area->free_list[migratetype]))
1041                                 continue;
1042
1043                         page = list_entry(area->free_list[migratetype].next,
1044                                         struct page, lru);
1045                         area->nr_free--;
1046
1047                         /*
1048                          * If breaking a large block of pages, move all free
1049                          * pages to the preferred allocation list. If falling
1050                          * back for a reclaimable kernel allocation, be more
1051                          * aggressive about taking ownership of free pages
1052                          *
1053                          * On the other hand, never change migration
1054                          * type of MIGRATE_CMA pageblocks nor move CMA
1055                          * pages on different free lists. We don't
1056                          * want unmovable pages to be allocated from
1057                          * MIGRATE_CMA areas.
1058                          */
1059                         if (!is_migrate_cma(migratetype) &&
1060                             (unlikely(current_order >= pageblock_order / 2) ||
1061                              start_migratetype == MIGRATE_RECLAIMABLE ||
1062                              page_group_by_mobility_disabled)) {
1063                                 int pages;
1064                                 pages = move_freepages_block(zone, page,
1065                                                                 start_migratetype);
1066
1067                                 /* Claim the whole block if over half of it is free */
1068                                 if (pages >= (1 << (pageblock_order-1)) ||
1069                                                 page_group_by_mobility_disabled)
1070                                         set_pageblock_migratetype(page,
1071                                                                 start_migratetype);
1072
1073                                 migratetype = start_migratetype;
1074                         }
1075
1076                         /* Remove the page from the freelists */
1077                         list_del(&page->lru);
1078                         rmv_page_order(page);
1079
1080                         /* Take ownership for orders >= pageblock_order */
1081                         if (current_order >= pageblock_order &&
1082                             !is_migrate_cma(migratetype))
1083                                 change_pageblock_range(page, current_order,
1084                                                         start_migratetype);
1085
1086                         expand(zone, page, order, current_order, area,
1087                                is_migrate_cma(migratetype)
1088                              ? migratetype : start_migratetype);
1089
1090                         trace_mm_page_alloc_extfrag(page, order, current_order,
1091                                 start_migratetype, migratetype);
1092
1093                         return page;
1094                 }
1095         }
1096
1097         return NULL;
1098 }
1099
1100 /*
1101  * Do the hard work of removing an element from the buddy allocator.
1102  * Call me with the zone->lock already held.
1103  */
1104 static struct page *__rmqueue(struct zone *zone, unsigned int order,
1105                                                 int migratetype)
1106 {
1107         struct page *page;
1108
1109 retry_reserve:
1110         page = __rmqueue_smallest(zone, order, migratetype);
1111
1112         if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
1113                 page = __rmqueue_fallback(zone, order, migratetype);
1114
1115                 /*
1116                  * Use MIGRATE_RESERVE rather than fail an allocation. goto
1117                  * is used because __rmqueue_smallest is an inline function
1118                  * and we want just one call site
1119                  */
1120                 if (!page) {
1121                         migratetype = MIGRATE_RESERVE;
1122                         goto retry_reserve;
1123                 }
1124         }
1125
1126         trace_mm_page_alloc_zone_locked(page, order, migratetype);
1127         return page;
1128 }
1129
1130 /*
1131  * Obtain a specified number of elements from the buddy allocator, all under
1132  * a single hold of the lock, for efficiency.  Add them to the supplied list.
1133  * Returns the number of new pages which were placed at *list.
1134  */
1135 static int rmqueue_bulk(struct zone *zone, unsigned int order,
1136                         unsigned long count, struct list_head *list,
1137                         int migratetype, int cold)
1138 {
1139         int mt = migratetype, i;
1140
1141         spin_lock(&zone->lock);
1142         for (i = 0; i < count; ++i) {
1143                 struct page *page = __rmqueue(zone, order, migratetype);
1144                 if (unlikely(page == NULL))
1145                         break;
1146
1147                 /*
1148                  * Split buddy pages returned by expand() are received here
1149                  * in physical page order. The page is added to the callers and
1150                  * list and the list head then moves forward. From the callers
1151                  * perspective, the linked list is ordered by page number in
1152                  * some conditions. This is useful for IO devices that can
1153                  * merge IO requests if the physical pages are ordered
1154                  * properly.
1155                  */
1156                 if (likely(cold == 0))
1157                         list_add(&page->lru, list);
1158                 else
1159                         list_add_tail(&page->lru, list);
1160                 if (IS_ENABLED(CONFIG_CMA)) {
1161                         mt = get_pageblock_migratetype(page);
1162                         if (!is_migrate_cma(mt) && mt != MIGRATE_ISOLATE)
1163                                 mt = migratetype;
1164                 }
1165                 set_page_private(page, mt);
1166                 list = &page->lru;
1167         }
1168         __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
1169         spin_unlock(&zone->lock);
1170         return i;
1171 }
1172
1173 #ifdef CONFIG_NUMA
1174 /*
1175  * Called from the vmstat counter updater to drain pagesets of this
1176  * currently executing processor on remote nodes after they have
1177  * expired.
1178  *
1179  * Note that this function must be called with the thread pinned to
1180  * a single processor.
1181  */
1182 void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
1183 {
1184         unsigned long flags;
1185         int to_drain;
1186
1187         local_irq_save(flags);
1188         if (pcp->count >= pcp->batch)
1189                 to_drain = pcp->batch;
1190         else
1191                 to_drain = pcp->count;
1192         free_pcppages_bulk(zone, to_drain, pcp);
1193         pcp->count -= to_drain;
1194         local_irq_restore(flags);
1195 }
1196 #endif
1197
1198 /*
1199  * Drain pages of the indicated processor.
1200  *
1201  * The processor must either be the current processor and the
1202  * thread pinned to the current processor or a processor that
1203  * is not online.
1204  */
1205 static void drain_pages(unsigned int cpu)
1206 {
1207         unsigned long flags;
1208         struct zone *zone;
1209
1210         for_each_populated_zone(zone) {
1211                 struct per_cpu_pageset *pset;
1212                 struct per_cpu_pages *pcp;
1213
1214                 local_irq_save(flags);
1215                 pset = per_cpu_ptr(zone->pageset, cpu);
1216
1217                 pcp = &pset->pcp;
1218                 if (pcp->count) {
1219                         free_pcppages_bulk(zone, pcp->count, pcp);
1220                         pcp->count = 0;
1221                 }
1222                 local_irq_restore(flags);
1223         }
1224 }
1225
1226 /*
1227  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
1228  */
1229 void drain_local_pages(void *arg)
1230 {
1231         drain_pages(smp_processor_id());
1232 }
1233
1234 /*
1235  * Spill all the per-cpu pages from all CPUs back into the buddy allocator
1236  */
1237 void drain_all_pages(void)
1238 {
1239         on_each_cpu(drain_local_pages, NULL, 1);
1240 }
1241
1242 #ifdef CONFIG_HIBERNATION
1243
1244 void mark_free_pages(struct zone *zone)
1245 {
1246         unsigned long pfn, max_zone_pfn;
1247         unsigned long flags;
1248         int order, t;
1249         struct list_head *curr;
1250
1251         if (!zone->spanned_pages)
1252                 return;
1253
1254         spin_lock_irqsave(&zone->lock, flags);
1255
1256         max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
1257         for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
1258                 if (pfn_valid(pfn)) {
1259                         struct page *page = pfn_to_page(pfn);
1260
1261                         if (!swsusp_page_is_forbidden(page))
1262                                 swsusp_unset_page_free(page);
1263                 }
1264
1265         for_each_migratetype_order(order, t) {
1266                 list_for_each(curr, &zone->free_area[order].free_list[t]) {
1267                         unsigned long i;
1268
1269                         pfn = page_to_pfn(list_entry(curr, struct page, lru));
1270                         for (i = 0; i < (1UL << order); i++)
1271                                 swsusp_set_page_free(pfn_to_page(pfn + i));
1272                 }
1273         }
1274         spin_unlock_irqrestore(&zone->lock, flags);
1275 }
1276 #endif /* CONFIG_PM */
1277
1278 /*
1279  * Free a 0-order page
1280  * cold == 1 ? free a cold page : free a hot page
1281  */
1282 void free_hot_cold_page(struct page *page, int cold)
1283 {
1284         struct zone *zone = page_zone(page);
1285         struct per_cpu_pages *pcp;
1286         unsigned long flags;
1287         int migratetype;
1288         int wasMlocked = __TestClearPageMlocked(page);
1289
1290         if (!free_pages_prepare(page, 0))
1291                 return;
1292
1293         migratetype = get_pageblock_migratetype(page);
1294         set_page_private(page, migratetype);
1295         local_irq_save(flags);
1296         if (unlikely(wasMlocked))
1297                 free_page_mlock(page);
1298         __count_vm_event(PGFREE);
1299
1300         /*
1301          * We only track unmovable, reclaimable and movable on pcp lists.
1302          * Free ISOLATE pages back to the allocator because they are being
1303          * offlined but treat RESERVE as movable pages so we can get those
1304          * areas back if necessary. Otherwise, we may have to free
1305          * excessively into the page allocator
1306          */
1307         if (migratetype >= MIGRATE_PCPTYPES) {
1308                 if (unlikely(migratetype == MIGRATE_ISOLATE)) {
1309                         free_one_page(zone, page, 0, migratetype);
1310                         goto out;
1311                 }
1312                 migratetype = MIGRATE_MOVABLE;
1313         }
1314
1315         pcp = &this_cpu_ptr(zone->pageset)->pcp;
1316         if (cold)
1317                 list_add_tail(&page->lru, &pcp->lists[migratetype]);
1318         else
1319                 list_add(&page->lru, &pcp->lists[migratetype]);
1320         pcp->count++;
1321         if (pcp->count >= pcp->high) {
1322                 free_pcppages_bulk(zone, pcp->batch, pcp);
1323                 pcp->count -= pcp->batch;
1324         }
1325
1326 out:
1327         local_irq_restore(flags);
1328 }
1329
1330 /*
1331  * Free a list of 0-order pages
1332  */
1333 void free_hot_cold_page_list(struct list_head *list, int cold)
1334 {
1335         struct page *page, *next;
1336
1337         list_for_each_entry_safe(page, next, list, lru) {
1338                 trace_mm_page_free_batched(page, cold);
1339                 free_hot_cold_page(page, cold);
1340         }
1341 }
1342
1343 /*
1344  * split_page takes a non-compound higher-order page, and splits it into
1345  * n (1<<order) sub-pages: page[0..n]
1346  * Each sub-page must be freed individually.
1347  *
1348  * Note: this is probably too low level an operation for use in drivers.
1349  * Please consult with lkml before using this in your driver.
1350  */
1351 void split_page(struct page *page, unsigned int order)
1352 {
1353         int i;
1354
1355         VM_BUG_ON(PageCompound(page));
1356         VM_BUG_ON(!page_count(page));
1357
1358 #ifdef CONFIG_KMEMCHECK
1359         /*
1360          * Split shadow pages too, because free(page[0]) would
1361          * otherwise free the whole shadow.
1362          */
1363         if (kmemcheck_page_is_tracked(page))
1364                 split_page(virt_to_page(page[0].shadow), order);
1365 #endif
1366
1367         for (i = 1; i < (1 << order); i++)
1368                 set_page_refcounted(page + i);
1369 }
1370
1371 /*
1372  * Similar to split_page except the page is already free. As this is only
1373  * being used for migration, the migratetype of the block also changes.
1374  * As this is called with interrupts disabled, the caller is responsible
1375  * for calling arch_alloc_page() and kernel_map_page() after interrupts
1376  * are enabled.
1377  *
1378  * Note: this is probably too low level an operation for use in drivers.
1379  * Please consult with lkml before using this in your driver.
1380  */
1381 int split_free_page(struct page *page)
1382 {
1383         unsigned int order;
1384         unsigned long watermark;
1385         struct zone *zone;
1386
1387         BUG_ON(!PageBuddy(page));
1388
1389         zone = page_zone(page);
1390         order = page_order(page);
1391
1392         /* Obey watermarks as if the page was being allocated */
1393         watermark = low_wmark_pages(zone) + (1 << order);
1394         if (!zone_watermark_ok(zone, 0, watermark, 0, 0))
1395                 return 0;
1396
1397         /* Remove page from free list */
1398         list_del(&page->lru);
1399         zone->free_area[order].nr_free--;
1400         rmv_page_order(page);
1401         __mod_zone_page_state(zone, NR_FREE_PAGES, -(1UL << order));
1402
1403         /* Split into individual pages */
1404         set_page_refcounted(page);
1405         split_page(page, order);
1406
1407         if (order >= pageblock_order - 1) {
1408                 struct page *endpage = page + (1 << order) - 1;
1409                 for (; page < endpage; page += pageblock_nr_pages) {
1410                         int mt = get_pageblock_migratetype(page);
1411                         if (mt != MIGRATE_ISOLATE && !is_migrate_cma(mt))
1412                                 set_pageblock_migratetype(page,
1413                                                           MIGRATE_MOVABLE);
1414                 }
1415         }
1416
1417         return 1 << order;
1418 }
1419
1420 /*
1421  * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
1422  * we cheat by calling it from here, in the order > 0 path.  Saves a branch
1423  * or two.
1424  */
1425 static inline
1426 struct page *buffered_rmqueue(struct zone *preferred_zone,
1427                         struct zone *zone, int order, gfp_t gfp_flags,
1428                         int migratetype)
1429 {
1430         unsigned long flags;
1431         struct page *page;
1432         int cold = !!(gfp_flags & __GFP_COLD);
1433
1434 again:
1435         if (likely(order == 0)) {
1436                 struct per_cpu_pages *pcp;
1437                 struct list_head *list;
1438
1439                 local_irq_save(flags);
1440                 pcp = &this_cpu_ptr(zone->pageset)->pcp;
1441                 list = &pcp->lists[migratetype];
1442                 if (list_empty(list)) {
1443                         pcp->count += rmqueue_bulk(zone, 0,
1444                                         pcp->batch, list,
1445                                         migratetype, cold);
1446                         if (unlikely(list_empty(list)))
1447                                 goto failed;
1448                 }
1449
1450                 if (cold)
1451                         page = list_entry(list->prev, struct page, lru);
1452                 else
1453                         page = list_entry(list->next, struct page, lru);
1454
1455                 list_del(&page->lru);
1456                 pcp->count--;
1457         } else {
1458                 if (unlikely(gfp_flags & __GFP_NOFAIL)) {
1459                         /*
1460                          * __GFP_NOFAIL is not to be used in new code.
1461                          *
1462                          * All __GFP_NOFAIL callers should be fixed so that they
1463                          * properly detect and handle allocation failures.
1464                          *
1465                          * We most definitely don't want callers attempting to
1466                          * allocate greater than order-1 page units with
1467                          * __GFP_NOFAIL.
1468                          */
1469                         WARN_ON_ONCE(order > 1);
1470                 }
1471                 spin_lock_irqsave(&zone->lock, flags);
1472                 page = __rmqueue(zone, order, migratetype);
1473                 spin_unlock(&zone->lock);
1474                 if (!page)
1475                         goto failed;
1476                 __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));
1477         }
1478
1479         __count_zone_vm_events(PGALLOC, zone, 1 << order);
1480         zone_statistics(preferred_zone, zone, gfp_flags);
1481         local_irq_restore(flags);
1482
1483         VM_BUG_ON(bad_range(zone, page));
1484         if (prep_new_page(page, order, gfp_flags))
1485                 goto again;
1486         return page;
1487
1488 failed:
1489         local_irq_restore(flags);
1490         return NULL;
1491 }
1492
1493 /* The ALLOC_WMARK bits are used as an index to zone->watermark */
1494 #define ALLOC_WMARK_MIN         WMARK_MIN
1495 #define ALLOC_WMARK_LOW         WMARK_LOW
1496 #define ALLOC_WMARK_HIGH        WMARK_HIGH
1497 #define ALLOC_NO_WATERMARKS     0x04 /* don't check watermarks at all */
1498
1499 /* Mask to get the watermark bits */
1500 #define ALLOC_WMARK_MASK        (ALLOC_NO_WATERMARKS-1)
1501
1502 #define ALLOC_HARDER            0x10 /* try to alloc harder */
1503 #define ALLOC_HIGH              0x20 /* __GFP_HIGH set */
1504 #define ALLOC_CPUSET            0x40 /* check for correct cpuset */
1505
1506 #ifdef CONFIG_FAIL_PAGE_ALLOC
1507
1508 static struct {
1509         struct fault_attr attr;
1510
1511         u32 ignore_gfp_highmem;
1512         u32 ignore_gfp_wait;
1513         u32 min_order;
1514 } fail_page_alloc = {
1515         .attr = FAULT_ATTR_INITIALIZER,
1516         .ignore_gfp_wait = 1,
1517         .ignore_gfp_highmem = 1,
1518         .min_order = 1,
1519 };
1520
1521 static int __init setup_fail_page_alloc(char *str)
1522 {
1523         return setup_fault_attr(&fail_page_alloc.attr, str);
1524 }
1525 __setup("fail_page_alloc=", setup_fail_page_alloc);
1526
1527 static int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1528 {
1529         if (order < fail_page_alloc.min_order)
1530                 return 0;
1531         if (gfp_mask & __GFP_NOFAIL)
1532                 return 0;
1533         if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
1534                 return 0;
1535         if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT))
1536                 return 0;
1537
1538         return should_fail(&fail_page_alloc.attr, 1 << order);
1539 }
1540
1541 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
1542
1543 static int __init fail_page_alloc_debugfs(void)
1544 {
1545         umode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
1546         struct dentry *dir;
1547
1548         dir = fault_create_debugfs_attr("fail_page_alloc", NULL,
1549                                         &fail_page_alloc.attr);
1550         if (IS_ERR(dir))
1551                 return PTR_ERR(dir);
1552
1553         if (!debugfs_create_bool("ignore-gfp-wait", mode, dir,
1554                                 &fail_page_alloc.ignore_gfp_wait))
1555                 goto fail;
1556         if (!debugfs_create_bool("ignore-gfp-highmem", mode, dir,
1557                                 &fail_page_alloc.ignore_gfp_highmem))
1558                 goto fail;
1559         if (!debugfs_create_u32("min-order", mode, dir,
1560                                 &fail_page_alloc.min_order))
1561                 goto fail;
1562
1563         return 0;
1564 fail:
1565         debugfs_remove_recursive(dir);
1566
1567         return -ENOMEM;
1568 }
1569
1570 late_initcall(fail_page_alloc_debugfs);
1571
1572 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
1573
1574 #else /* CONFIG_FAIL_PAGE_ALLOC */
1575
1576 static inline int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1577 {
1578         return 0;
1579 }
1580
1581 #endif /* CONFIG_FAIL_PAGE_ALLOC */
1582
1583 /*
1584  * Return true if free pages are above 'mark'. This takes into account the order
1585  * of the allocation.
1586  */
1587 static bool __zone_watermark_ok(struct zone *z, int order, unsigned long mark,
1588                       int classzone_idx, int alloc_flags, long free_pages)
1589 {
1590         /* free_pages my go negative - that's OK */
1591         long min = mark;
1592         int o;
1593
1594         free_pages -= (1 << order) - 1;
1595         if (alloc_flags & ALLOC_HIGH)
1596                 min -= min / 2;
1597         if (alloc_flags & ALLOC_HARDER)
1598                 min -= min / 4;
1599
1600         if (free_pages <= min + z->lowmem_reserve[classzone_idx])
1601                 return false;
1602         for (o = 0; o < order; o++) {
1603                 /* At the next order, this order's pages become unavailable */
1604                 free_pages -= z->free_area[o].nr_free << o;
1605
1606                 /* Require fewer higher order pages to be free */
1607                 min >>= 1;
1608
1609                 if (free_pages <= min)
1610                         return false;
1611         }
1612         return true;
1613 }
1614
1615 bool zone_watermark_ok(struct zone *z, int order, unsigned long mark,
1616                       int classzone_idx, int alloc_flags)
1617 {
1618         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
1619                                         zone_page_state(z, NR_FREE_PAGES));
1620 }
1621
1622 bool zone_watermark_ok_safe(struct zone *z, int order, unsigned long mark,
1623                       int classzone_idx, int alloc_flags)
1624 {
1625         long free_pages = zone_page_state(z, NR_FREE_PAGES);
1626
1627         if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
1628                 free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);
1629
1630         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
1631                                                                 free_pages);
1632 }
1633
1634 #ifdef CONFIG_NUMA
1635 /*
1636  * zlc_setup - Setup for "zonelist cache".  Uses cached zone data to
1637  * skip over zones that are not allowed by the cpuset, or that have
1638  * been recently (in last second) found to be nearly full.  See further
1639  * comments in mmzone.h.  Reduces cache footprint of zonelist scans
1640  * that have to skip over a lot of full or unallowed zones.
1641  *
1642  * If the zonelist cache is present in the passed in zonelist, then
1643  * returns a pointer to the allowed node mask (either the current
1644  * tasks mems_allowed, or node_states[N_HIGH_MEMORY].)
1645  *
1646  * If the zonelist cache is not available for this zonelist, does
1647  * nothing and returns NULL.
1648  *
1649  * If the fullzones BITMAP in the zonelist cache is stale (more than
1650  * a second since last zap'd) then we zap it out (clear its bits.)
1651  *
1652  * We hold off even calling zlc_setup, until after we've checked the
1653  * first zone in the zonelist, on the theory that most allocations will
1654  * be satisfied from that first zone, so best to examine that zone as
1655  * quickly as we can.
1656  */
1657 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1658 {
1659         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1660         nodemask_t *allowednodes;       /* zonelist_cache approximation */
1661
1662         zlc = zonelist->zlcache_ptr;
1663         if (!zlc)
1664                 return NULL;
1665
1666         if (time_after(jiffies, zlc->last_full_zap + HZ)) {
1667                 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1668                 zlc->last_full_zap = jiffies;
1669         }
1670
1671         allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ?
1672                                         &cpuset_current_mems_allowed :
1673                                         &node_states[N_HIGH_MEMORY];
1674         return allowednodes;
1675 }
1676
1677 /*
1678  * Given 'z' scanning a zonelist, run a couple of quick checks to see
1679  * if it is worth looking at further for free memory:
1680  *  1) Check that the zone isn't thought to be full (doesn't have its
1681  *     bit set in the zonelist_cache fullzones BITMAP).
1682  *  2) Check that the zones node (obtained from the zonelist_cache
1683  *     z_to_n[] mapping) is allowed in the passed in allowednodes mask.
1684  * Return true (non-zero) if zone is worth looking at further, or
1685  * else return false (zero) if it is not.
1686  *
1687  * This check -ignores- the distinction between various watermarks,
1688  * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ...  If a zone is
1689  * found to be full for any variation of these watermarks, it will
1690  * be considered full for up to one second by all requests, unless
1691  * we are so low on memory on all allowed nodes that we are forced
1692  * into the second scan of the zonelist.
1693  *
1694  * In the second scan we ignore this zonelist cache and exactly
1695  * apply the watermarks to all zones, even it is slower to do so.
1696  * We are low on memory in the second scan, and should leave no stone
1697  * unturned looking for a free page.
1698  */
1699 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1700                                                 nodemask_t *allowednodes)
1701 {
1702         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1703         int i;                          /* index of *z in zonelist zones */
1704         int n;                          /* node that zone *z is on */
1705
1706         zlc = zonelist->zlcache_ptr;
1707         if (!zlc)
1708                 return 1;
1709
1710         i = z - zonelist->_zonerefs;
1711         n = zlc->z_to_n[i];
1712
1713         /* This zone is worth trying if it is allowed but not full */
1714         return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones);
1715 }
1716
1717 /*
1718  * Given 'z' scanning a zonelist, set the corresponding bit in
1719  * zlc->fullzones, so that subsequent attempts to allocate a page
1720  * from that zone don't waste time re-examining it.
1721  */
1722 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1723 {
1724         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1725         int i;                          /* index of *z in zonelist zones */
1726
1727         zlc = zonelist->zlcache_ptr;
1728         if (!zlc)
1729                 return;
1730
1731         i = z - zonelist->_zonerefs;
1732
1733         set_bit(i, zlc->fullzones);
1734 }
1735
1736 /*
1737  * clear all zones full, called after direct reclaim makes progress so that
1738  * a zone that was recently full is not skipped over for up to a second
1739  */
1740 static void zlc_clear_zones_full(struct zonelist *zonelist)
1741 {
1742         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1743
1744         zlc = zonelist->zlcache_ptr;
1745         if (!zlc)
1746                 return;
1747
1748         bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1749 }
1750
1751 #else   /* CONFIG_NUMA */
1752
1753 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1754 {
1755         return NULL;
1756 }
1757
1758 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1759                                 nodemask_t *allowednodes)
1760 {
1761         return 1;
1762 }
1763
1764 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1765 {
1766 }
1767
1768 static void zlc_clear_zones_full(struct zonelist *zonelist)
1769 {
1770 }
1771 #endif  /* CONFIG_NUMA */
1772
1773 /*
1774  * get_page_from_freelist goes through the zonelist trying to allocate
1775  * a page.
1776  */
1777 static struct page *
1778 get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
1779                 struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
1780                 struct zone *preferred_zone, int migratetype)
1781 {
1782         struct zoneref *z;
1783         struct page *page = NULL;
1784         int classzone_idx;
1785         struct zone *zone;
1786         nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
1787         int zlc_active = 0;             /* set if using zonelist_cache */
1788         int did_zlc_setup = 0;          /* just call zlc_setup() one time */
1789
1790         classzone_idx = zone_idx(preferred_zone);
1791 zonelist_scan:
1792         /*
1793          * Scan zonelist, looking for a zone with enough free.
1794          * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1795          */
1796         for_each_zone_zonelist_nodemask(zone, z, zonelist,
1797                                                 high_zoneidx, nodemask) {
1798                 if (NUMA_BUILD && zlc_active &&
1799                         !zlc_zone_worth_trying(zonelist, z, allowednodes))
1800                                 continue;
1801                 if ((alloc_flags & ALLOC_CPUSET) &&
1802                         !cpuset_zone_allowed_softwall(zone, gfp_mask))
1803                                 continue;
1804
1805                 BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
1806                 if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
1807                         unsigned long mark;
1808                         int ret;
1809
1810                         mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
1811                         if (zone_watermark_ok(zone, order, mark,
1812                                     classzone_idx, alloc_flags))
1813                                 goto try_this_zone;
1814
1815                         if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {
1816                                 /*
1817                                  * we do zlc_setup if there are multiple nodes
1818                                  * and before considering the first zone allowed
1819                                  * by the cpuset.
1820                                  */
1821                                 allowednodes = zlc_setup(zonelist, alloc_flags);
1822                                 zlc_active = 1;
1823                                 did_zlc_setup = 1;
1824                         }
1825
1826                         if (zone_reclaim_mode == 0)
1827                                 goto this_zone_full;
1828
1829                         /*
1830                          * As we may have just activated ZLC, check if the first
1831                          * eligible zone has failed zone_reclaim recently.
1832                          */
1833                         if (NUMA_BUILD && zlc_active &&
1834                                 !zlc_zone_worth_trying(zonelist, z, allowednodes))
1835                                 continue;
1836
1837                         ret = zone_reclaim(zone, gfp_mask, order);
1838                         switch (ret) {
1839                         case ZONE_RECLAIM_NOSCAN:
1840                                 /* did not scan */
1841                                 continue;
1842                         case ZONE_RECLAIM_FULL:
1843                                 /* scanned but unreclaimable */
1844                                 continue;
1845                         default:
1846                                 /* did we reclaim enough */
1847                                 if (!zone_watermark_ok(zone, order, mark,
1848                                                 classzone_idx, alloc_flags))
1849                                         goto this_zone_full;
1850                         }
1851                 }
1852
1853 try_this_zone:
1854                 page = buffered_rmqueue(preferred_zone, zone, order,
1855                                                 gfp_mask, migratetype);
1856                 if (page)
1857                         break;
1858 this_zone_full:
1859                 if (NUMA_BUILD)
1860                         zlc_mark_zone_full(zonelist, z);
1861         }
1862
1863         if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
1864                 /* Disable zlc cache for second zonelist scan */
1865                 zlc_active = 0;
1866                 goto zonelist_scan;
1867         }
1868         return page;
1869 }
1870
1871 /*
1872  * Large machines with many possible nodes should not always dump per-node
1873  * meminfo in irq context.
1874  */
1875 static inline bool should_suppress_show_mem(void)
1876 {
1877         bool ret = false;
1878
1879 #if NODES_SHIFT > 8
1880         ret = in_interrupt();
1881 #endif
1882         return ret;
1883 }
1884
1885 static DEFINE_RATELIMIT_STATE(nopage_rs,
1886                 DEFAULT_RATELIMIT_INTERVAL,
1887                 DEFAULT_RATELIMIT_BURST);
1888
1889 void warn_alloc_failed(gfp_t gfp_mask, int order, const char *fmt, ...)
1890 {
1891         unsigned int filter = SHOW_MEM_FILTER_NODES;
1892
1893         if ((gfp_mask & __GFP_NOWARN) || !__ratelimit(&nopage_rs) ||
1894             debug_guardpage_minorder() > 0)
1895                 return;
1896
1897         /*
1898          * This documents exceptions given to allocations in certain
1899          * contexts that are allowed to allocate outside current's set
1900          * of allowed nodes.
1901          */
1902         if (!(gfp_mask & __GFP_NOMEMALLOC))
1903                 if (test_thread_flag(TIF_MEMDIE) ||
1904                     (current->flags & (PF_MEMALLOC | PF_EXITING)))
1905                         filter &= ~SHOW_MEM_FILTER_NODES;
1906         if (in_interrupt() || !(gfp_mask & __GFP_WAIT))
1907                 filter &= ~SHOW_MEM_FILTER_NODES;
1908
1909         if (fmt) {
1910                 struct va_format vaf;
1911                 va_list args;
1912
1913                 va_start(args, fmt);
1914
1915                 vaf.fmt = fmt;
1916                 vaf.va = &args;
1917
1918                 pr_warn("%pV", &vaf);
1919
1920                 va_end(args);
1921         }
1922
1923         pr_warn("%s: page allocation failure: order:%d, mode:0x%x\n",
1924                 current->comm, order, gfp_mask);
1925
1926         dump_stack();
1927         if (!should_suppress_show_mem())
1928                 show_mem(filter);
1929 }
1930
1931 static inline int
1932 should_alloc_retry(gfp_t gfp_mask, unsigned int order,
1933                                 unsigned long did_some_progress,
1934                                 unsigned long pages_reclaimed)
1935 {
1936         /* Do not loop if specifically requested */
1937         if (gfp_mask & __GFP_NORETRY)
1938                 return 0;
1939
1940         /* Always retry if specifically requested */
1941         if (gfp_mask & __GFP_NOFAIL)
1942                 return 1;
1943
1944         /*
1945          * Suspend converts GFP_KERNEL to __GFP_WAIT which can prevent reclaim
1946          * making forward progress without invoking OOM. Suspend also disables
1947          * storage devices so kswapd will not help. Bail if we are suspending.
1948          */
1949         if (!did_some_progress && pm_suspended_storage())
1950                 return 0;
1951
1952         /*
1953          * In this implementation, order <= PAGE_ALLOC_COSTLY_ORDER
1954          * means __GFP_NOFAIL, but that may not be true in other
1955          * implementations.
1956          */
1957         if (order <= PAGE_ALLOC_COSTLY_ORDER)
1958                 return 1;
1959
1960         /*
1961          * For order > PAGE_ALLOC_COSTLY_ORDER, if __GFP_REPEAT is
1962          * specified, then we retry until we no longer reclaim any pages
1963          * (above), or we've reclaimed an order of pages at least as
1964          * large as the allocation's order. In both cases, if the
1965          * allocation still fails, we stop retrying.
1966          */
1967         if (gfp_mask & __GFP_REPEAT && pages_reclaimed < (1 << order))
1968                 return 1;
1969
1970         return 0;
1971 }
1972
1973 static inline struct page *
1974 __alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
1975         struct zonelist *zonelist, enum zone_type high_zoneidx,
1976         nodemask_t *nodemask, struct zone *preferred_zone,
1977         int migratetype)
1978 {
1979         struct page *page;
1980
1981         /* Acquire the OOM killer lock for the zones in zonelist */
1982         if (!try_set_zonelist_oom(zonelist, gfp_mask)) {
1983                 schedule_timeout_uninterruptible(1);
1984                 return NULL;
1985         }
1986
1987         /*
1988          * Go through the zonelist yet one more time, keep very high watermark
1989          * here, this is only to catch a parallel oom killing, we must fail if
1990          * we're still under heavy pressure.
1991          */
1992         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask,
1993                 order, zonelist, high_zoneidx,
1994                 ALLOC_WMARK_HIGH|ALLOC_CPUSET,
1995                 preferred_zone, migratetype);
1996         if (page)
1997                 goto out;
1998
1999         if (!(gfp_mask & __GFP_NOFAIL)) {
2000                 /* The OOM killer will not help higher order allocs */
2001                 if (order > PAGE_ALLOC_COSTLY_ORDER)
2002                         goto out;
2003                 /* The OOM killer does not needlessly kill tasks for lowmem */
2004                 if (high_zoneidx < ZONE_NORMAL)
2005                         goto out;
2006                 /*
2007                  * GFP_THISNODE contains __GFP_NORETRY and we never hit this.
2008                  * Sanity check for bare calls of __GFP_THISNODE, not real OOM.
2009                  * The caller should handle page allocation failure by itself if
2010                  * it specifies __GFP_THISNODE.
2011                  * Note: Hugepage uses it but will hit PAGE_ALLOC_COSTLY_ORDER.
2012                  */
2013                 if (gfp_mask & __GFP_THISNODE)
2014                         goto out;
2015         }
2016         /* Exhausted what can be done so it's blamo time */
2017         out_of_memory(zonelist, gfp_mask, order, nodemask);
2018
2019 out:
2020         clear_zonelist_oom(zonelist, gfp_mask);
2021         return page;
2022 }
2023
2024 #ifdef CONFIG_COMPACTION
2025 /* Try memory compaction for high-order allocations before reclaim */
2026 static struct page *
2027 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
2028         struct zonelist *zonelist, enum zone_type high_zoneidx,
2029         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
2030         int migratetype, bool sync_migration,
2031         bool *deferred_compaction,
2032         unsigned long *did_some_progress)
2033 {
2034         struct page *page;
2035
2036         if (!order)
2037                 return NULL;
2038
2039         if (compaction_deferred(preferred_zone)) {
2040                 *deferred_compaction = true;
2041                 return NULL;
2042         }
2043
2044         current->flags |= PF_MEMALLOC;
2045         *did_some_progress = try_to_compact_pages(zonelist, order, gfp_mask,
2046                                                 nodemask, sync_migration);
2047         current->flags &= ~PF_MEMALLOC;
2048         if (*did_some_progress != COMPACT_SKIPPED) {
2049
2050                 /* Page migration frees to the PCP lists but we want merging */
2051                 drain_pages(get_cpu());
2052                 put_cpu();
2053
2054                 page = get_page_from_freelist(gfp_mask, nodemask,
2055                                 order, zonelist, high_zoneidx,
2056                                 alloc_flags, preferred_zone,
2057                                 migratetype);
2058                 if (page) {
2059                         preferred_zone->compact_considered = 0;
2060                         preferred_zone->compact_defer_shift = 0;
2061                         count_vm_event(COMPACTSUCCESS);
2062                         return page;
2063                 }
2064
2065                 /*
2066                  * It's bad if compaction run occurs and fails.
2067                  * The most likely reason is that pages exist,
2068                  * but not enough to satisfy watermarks.
2069                  */
2070                 count_vm_event(COMPACTFAIL);
2071
2072                 /*
2073                  * As async compaction considers a subset of pageblocks, only
2074                  * defer if the failure was a sync compaction failure.
2075                  */
2076                 if (sync_migration)
2077                         defer_compaction(preferred_zone);
2078
2079                 cond_resched();
2080         }
2081
2082         return NULL;
2083 }
2084 #else
2085 static inline struct page *
2086 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
2087         struct zonelist *zonelist, enum zone_type high_zoneidx,
2088         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
2089         int migratetype, bool sync_migration,
2090         bool *deferred_compaction,
2091         unsigned long *did_some_progress)
2092 {
2093         return NULL;
2094 }
2095 #endif /* CONFIG_COMPACTION */
2096
2097 /* Perform direct synchronous page reclaim */
2098 static int
2099 __perform_reclaim(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist,
2100                   nodemask_t *nodemask)
2101 {
2102         struct reclaim_state reclaim_state;
2103         int progress;
2104
2105         cond_resched();
2106
2107         /* We now go into synchronous reclaim */
2108         cpuset_memory_pressure_bump();
2109         current->flags |= PF_MEMALLOC;
2110         lockdep_set_current_reclaim_state(gfp_mask);
2111         reclaim_state.reclaimed_slab = 0;
2112         current->reclaim_state = &reclaim_state;
2113
2114         progress = try_to_free_pages(zonelist, order, gfp_mask, nodemask);
2115
2116         current->reclaim_state = NULL;
2117         lockdep_clear_current_reclaim_state();
2118         current->flags &= ~PF_MEMALLOC;
2119
2120         cond_resched();
2121
2122         return progress;
2123 }
2124
2125 /* The really slow allocator path where we enter direct reclaim */
2126 static inline struct page *
2127 __alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,
2128         struct zonelist *zonelist, enum zone_type high_zoneidx,
2129         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
2130         int migratetype, unsigned long *did_some_progress)
2131 {
2132         struct page *page = NULL;
2133         bool drained = false;
2134
2135         *did_some_progress = __perform_reclaim(gfp_mask, order, zonelist,
2136                                                nodemask);
2137         if (unlikely(!(*did_some_progress)))
2138                 return NULL;
2139
2140         /* After successful reclaim, reconsider all zones for allocation */
2141         if (NUMA_BUILD)
2142                 zlc_clear_zones_full(zonelist);
2143
2144 retry:
2145         page = get_page_from_freelist(gfp_mask, nodemask, order,
2146                                         zonelist, high_zoneidx,
2147                                         alloc_flags, preferred_zone,
2148                                         migratetype);
2149
2150         /*
2151          * If an allocation failed after direct reclaim, it could be because
2152          * pages are pinned on the per-cpu lists. Drain them and try again
2153          */
2154         if (!page && !drained) {
2155                 drain_all_pages();
2156                 drained = true;
2157                 goto retry;
2158         }
2159
2160         return page;
2161 }
2162
2163 /*
2164  * This is called in the allocator slow-path if the allocation request is of
2165  * sufficient urgency to ignore watermarks and take other desperate measures
2166  */
2167 static inline struct page *
2168 __alloc_pages_high_priority(gfp_t gfp_mask, unsigned int order,
2169         struct zonelist *zonelist, enum zone_type high_zoneidx,
2170         nodemask_t *nodemask, struct zone *preferred_zone,
2171         int migratetype)
2172 {
2173         struct page *page;
2174
2175         do {
2176                 page = get_page_from_freelist(gfp_mask, nodemask, order,
2177                         zonelist, high_zoneidx, ALLOC_NO_WATERMARKS,
2178                         preferred_zone, migratetype);
2179
2180                 if (!page && gfp_mask & __GFP_NOFAIL)
2181                         wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);
2182         } while (!page && (gfp_mask & __GFP_NOFAIL));
2183
2184         return page;
2185 }
2186
2187 static inline
2188 void wake_all_kswapd(unsigned int order, struct zonelist *zonelist,
2189                                                 enum zone_type high_zoneidx,
2190                                                 enum zone_type classzone_idx)
2191 {
2192         struct zoneref *z;
2193         struct zone *zone;
2194
2195         for_each_zone_zonelist(zone, z, zonelist, high_zoneidx)
2196                 wakeup_kswapd(zone, order, classzone_idx);
2197 }
2198
2199 static inline int
2200 gfp_to_alloc_flags(gfp_t gfp_mask)
2201 {
2202         int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
2203         const gfp_t wait = gfp_mask & __GFP_WAIT;
2204
2205         /* __GFP_HIGH is assumed to be the same as ALLOC_HIGH to save a branch. */
2206         BUILD_BUG_ON(__GFP_HIGH != (__force gfp_t) ALLOC_HIGH);
2207
2208         /*
2209          * The caller may dip into page reserves a bit more if the caller
2210          * cannot run direct reclaim, or if the caller has realtime scheduling
2211          * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
2212          * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
2213          */
2214         alloc_flags |= (__force int) (gfp_mask & __GFP_HIGH);
2215
2216         if (!wait) {
2217                 /*
2218                  * Not worth trying to allocate harder for
2219                  * __GFP_NOMEMALLOC even if it can't schedule.
2220                  */
2221                 if  (!(gfp_mask & __GFP_NOMEMALLOC))
2222                         alloc_flags |= ALLOC_HARDER;
2223                 /*
2224                  * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
2225                  * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
2226                  */
2227                 alloc_flags &= ~ALLOC_CPUSET;
2228         } else if (unlikely(rt_task(current)) && !in_interrupt())
2229                 alloc_flags |= ALLOC_HARDER;
2230
2231         if (likely(!(gfp_mask & __GFP_NOMEMALLOC))) {
2232                 if (!in_interrupt() &&
2233                     ((current->flags & PF_MEMALLOC) ||
2234                      unlikely(test_thread_flag(TIF_MEMDIE))))
2235                         alloc_flags |= ALLOC_NO_WATERMARKS;
2236         }
2237
2238         return alloc_flags;
2239 }
2240
2241 static inline struct page *
2242 __alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
2243         struct zonelist *zonelist, enum zone_type high_zoneidx,
2244         nodemask_t *nodemask, struct zone *preferred_zone,
2245         int migratetype)
2246 {
2247         const gfp_t wait = gfp_mask & __GFP_WAIT;
2248         struct page *page = NULL;
2249         int alloc_flags;
2250         unsigned long pages_reclaimed = 0;
2251         unsigned long did_some_progress;
2252         bool sync_migration = false;
2253         bool deferred_compaction = false;
2254
2255         /*
2256          * In the slowpath, we sanity check order to avoid ever trying to
2257          * reclaim >= MAX_ORDER areas which will never succeed. Callers may
2258          * be using allocators in order of preference for an area that is
2259          * too large.
2260          */
2261         if (order >= MAX_ORDER) {
2262                 WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
2263                 return NULL;
2264         }
2265
2266         /*
2267          * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
2268          * __GFP_NOWARN set) should not cause reclaim since the subsystem
2269          * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
2270          * using a larger set of nodes after it has established that the
2271          * allowed per node queues are empty and that nodes are
2272          * over allocated.
2273          */
2274         if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
2275                 goto nopage;
2276
2277 restart:
2278         if (!(gfp_mask & __GFP_NO_KSWAPD))
2279                 wake_all_kswapd(order, zonelist, high_zoneidx,
2280                                                 zone_idx(preferred_zone));
2281
2282         /*
2283          * OK, we're below the kswapd watermark and have kicked background
2284          * reclaim. Now things get more complex, so set up alloc_flags according
2285          * to how we want to proceed.
2286          */
2287         alloc_flags = gfp_to_alloc_flags(gfp_mask);
2288
2289         /*
2290          * Find the true preferred zone if the allocation is unconstrained by
2291          * cpusets.
2292          */
2293         if (!(alloc_flags & ALLOC_CPUSET) && !nodemask)
2294                 first_zones_zonelist(zonelist, high_zoneidx, NULL,
2295                                         &preferred_zone);
2296
2297 rebalance:
2298         /* This is the last chance, in general, before the goto nopage. */
2299         page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
2300                         high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
2301                         preferred_zone, migratetype);
2302         if (page)
2303                 goto got_pg;
2304
2305         /* Allocate without watermarks if the context allows */
2306         if (alloc_flags & ALLOC_NO_WATERMARKS) {
2307                 page = __alloc_pages_high_priority(gfp_mask, order,
2308                                 zonelist, high_zoneidx, nodemask,
2309                                 preferred_zone, migratetype);
2310                 if (page)
2311                         goto got_pg;
2312         }
2313
2314         /* Atomic allocations - we can't balance anything */
2315         if (!wait)
2316                 goto nopage;
2317
2318         /* Avoid recursion of direct reclaim */
2319         if (current->flags & PF_MEMALLOC)
2320                 goto nopage;
2321
2322         /* Avoid allocations with no watermarks from looping endlessly */
2323         if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
2324                 goto nopage;
2325
2326         /*
2327          * Try direct compaction. The first pass is asynchronous. Subsequent
2328          * attempts after direct reclaim are synchronous
2329          */
2330         page = __alloc_pages_direct_compact(gfp_mask, order,
2331                                         zonelist, high_zoneidx,
2332                                         nodemask,
2333                                         alloc_flags, preferred_zone,
2334                                         migratetype, sync_migration,
2335                                         &deferred_compaction,
2336                                         &did_some_progress);
2337         if (page)
2338                 goto got_pg;
2339         sync_migration = true;
2340
2341         /*
2342          * If compaction is deferred for high-order allocations, it is because
2343          * sync compaction recently failed. In this is the case and the caller
2344          * has requested the system not be heavily disrupted, fail the
2345          * allocation now instead of entering direct reclaim
2346          */
2347         if (deferred_compaction && (gfp_mask & __GFP_NO_KSWAPD))
2348                 goto nopage;
2349
2350         /* Try direct reclaim and then allocating */
2351         page = __alloc_pages_direct_reclaim(gfp_mask, order,
2352                                         zonelist, high_zoneidx,
2353                                         nodemask,
2354                                         alloc_flags, preferred_zone,
2355                                         migratetype, &did_some_progress);
2356         if (page)
2357                 goto got_pg;
2358
2359         /*
2360          * If we failed to make any progress reclaiming, then we are
2361          * running out of options and have to consider going OOM
2362          */
2363         if (!did_some_progress) {
2364                 if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
2365                         if (oom_killer_disabled)
2366                                 goto nopage;
2367                         page = __alloc_pages_may_oom(gfp_mask, order,
2368                                         zonelist, high_zoneidx,
2369                                         nodemask, preferred_zone,
2370                                         migratetype);
2371                         if (page)
2372                                 goto got_pg;
2373
2374                         if (!(gfp_mask & __GFP_NOFAIL)) {
2375                                 /*
2376                                  * The oom killer is not called for high-order
2377                                  * allocations that may fail, so if no progress
2378                                  * is being made, there are no other options and
2379                                  * retrying is unlikely to help.
2380                                  */
2381                                 if (order > PAGE_ALLOC_COSTLY_ORDER)
2382                                         goto nopage;
2383                                 /*
2384                                  * The oom killer is not called for lowmem
2385                                  * allocations to prevent needlessly killing
2386                                  * innocent tasks.
2387                                  */
2388                                 if (high_zoneidx < ZONE_NORMAL)
2389                                         goto nopage;
2390                         }
2391
2392                         goto restart;
2393                 }
2394         }
2395
2396         /* Check if we should retry the allocation */
2397         pages_reclaimed += did_some_progress;
2398         if (should_alloc_retry(gfp_mask, order, did_some_progress,
2399                                                 pages_reclaimed)) {
2400                 /* Wait for some write requests to complete then retry */
2401                 wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);
2402                 goto rebalance;
2403         } else {
2404                 /*
2405                  * High-order allocations do not necessarily loop after
2406                  * direct reclaim and reclaim/compaction depends on compaction
2407                  * being called after reclaim so call directly if necessary
2408                  */
2409                 page = __alloc_pages_direct_compact(gfp_mask, order,
2410                                         zonelist, high_zoneidx,
2411                                         nodemask,
2412                                         alloc_flags, preferred_zone,
2413                                         migratetype, sync_migration,
2414                                         &deferred_compaction,
2415                                         &did_some_progress);
2416                 if (page)
2417                         goto got_pg;
2418         }
2419
2420 nopage:
2421         warn_alloc_failed(gfp_mask, order, NULL);
2422         return page;
2423 got_pg:
2424         if (kmemcheck_enabled)
2425                 kmemcheck_pagealloc_alloc(page, order, gfp_mask);
2426         return page;
2427
2428 }
2429
2430 /*
2431  * This is the 'heart' of the zoned buddy allocator.
2432  */
2433 struct page *
2434 __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
2435                         struct zonelist *zonelist, nodemask_t *nodemask)
2436 {
2437         enum zone_type high_zoneidx = gfp_zone(gfp_mask);
2438         struct zone *preferred_zone;
2439         struct page *page = NULL;
2440         int migratetype = allocflags_to_migratetype(gfp_mask);
2441         unsigned int cpuset_mems_cookie;
2442
2443         gfp_mask &= gfp_allowed_mask;
2444
2445         lockdep_trace_alloc(gfp_mask);
2446
2447         might_sleep_if(gfp_mask & __GFP_WAIT);
2448
2449         if (should_fail_alloc_page(gfp_mask, order))
2450                 return NULL;
2451
2452         /*
2453          * Check the zones suitable for the gfp_mask contain at least one
2454          * valid zone. It's possible to have an empty zonelist as a result
2455          * of GFP_THISNODE and a memoryless node
2456          */
2457         if (unlikely(!zonelist->_zonerefs->zone))
2458                 return NULL;
2459
2460 retry_cpuset:
2461         cpuset_mems_cookie = get_mems_allowed();
2462
2463         /* The preferred zone is used for statistics later */
2464         first_zones_zonelist(zonelist, high_zoneidx,
2465                                 nodemask ? : &cpuset_current_mems_allowed,
2466                                 &preferred_zone);
2467         if (!preferred_zone)
2468                 goto out;
2469
2470         /* First allocation attempt */
2471         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
2472                         zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET,
2473                         preferred_zone, migratetype);
2474         if (unlikely(!page))
2475                 page = __alloc_pages_slowpath(gfp_mask, order,
2476                                 zonelist, high_zoneidx, nodemask,
2477                                 preferred_zone, migratetype);
2478
2479         trace_mm_page_alloc(page, order, gfp_mask, migratetype);
2480
2481 out:
2482         /*
2483          * When updating a task's mems_allowed, it is possible to race with
2484          * parallel threads in such a way that an allocation can fail while
2485          * the mask is being updated. If a page allocation is about to fail,
2486          * check if the cpuset changed during allocation and if so, retry.
2487          */
2488         if (unlikely(!put_mems_allowed(cpuset_mems_cookie) && !page))
2489                 goto retry_cpuset;
2490
2491         return page;
2492 }
2493 EXPORT_SYMBOL(__alloc_pages_nodemask);
2494
2495 /*
2496  * Common helper functions.
2497  */
2498 unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
2499 {
2500         struct page *page;
2501
2502         /*
2503          * __get_free_pages() returns a 32-bit address, which cannot represent
2504          * a highmem page
2505          */
2506         VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
2507
2508         page = alloc_pages(gfp_mask, order);
2509         if (!page)
2510                 return 0;
2511         return (unsigned long) page_address(page);
2512 }
2513 EXPORT_SYMBOL(__get_free_pages);
2514
2515 unsigned long get_zeroed_page(gfp_t gfp_mask)
2516 {
2517         return __get_free_pages(gfp_mask | __GFP_ZERO, 0);
2518 }
2519 EXPORT_SYMBOL(get_zeroed_page);
2520
2521 void __free_pages(struct page *page, unsigned int order)
2522 {
2523         if (put_page_testzero(page)) {
2524                 if (order == 0)
2525                         free_hot_cold_page(page, 0);
2526                 else
2527                         __free_pages_ok(page, order);
2528         }
2529 }
2530
2531 EXPORT_SYMBOL(__free_pages);
2532
2533 void free_pages(unsigned long addr, unsigned int order)
2534 {
2535         if (addr != 0) {
2536                 VM_BUG_ON(!virt_addr_valid((void *)addr));
2537                 __free_pages(virt_to_page((void *)addr), order);
2538         }
2539 }
2540
2541 EXPORT_SYMBOL(free_pages);
2542
2543 static void *make_alloc_exact(unsigned long addr, unsigned order, size_t size)
2544 {
2545         if (addr) {
2546                 unsigned long alloc_end = addr + (PAGE_SIZE << order);
2547                 unsigned long used = addr + PAGE_ALIGN(size);
2548
2549                 split_page(virt_to_page((void *)addr), order);
2550                 while (used < alloc_end) {
2551                         free_page(used);
2552                         used += PAGE_SIZE;
2553                 }
2554         }
2555         return (void *)addr;
2556 }
2557
2558 /**
2559  * alloc_pages_exact - allocate an exact number physically-contiguous pages.
2560  * @size: the number of bytes to allocate
2561  * @gfp_mask: GFP flags for the allocation
2562  *
2563  * This function is similar to alloc_pages(), except that it allocates the
2564  * minimum number of pages to satisfy the request.  alloc_pages() can only
2565  * allocate memory in power-of-two pages.
2566  *
2567  * This function is also limited by MAX_ORDER.
2568  *
2569  * Memory allocated by this function must be released by free_pages_exact().
2570  */
2571 void *alloc_pages_exact(size_t size, gfp_t gfp_mask)
2572 {
2573         unsigned int order = get_order(size);
2574         unsigned long addr;
2575
2576         addr = __get_free_pages(gfp_mask, order);
2577         return make_alloc_exact(addr, order, size);
2578 }
2579 EXPORT_SYMBOL(alloc_pages_exact);
2580
2581 /**
2582  * alloc_pages_exact_nid - allocate an exact number of physically-contiguous
2583  *                         pages on a node.
2584  * @nid: the preferred node ID where memory should be allocated
2585  * @size: the number of bytes to allocate
2586  * @gfp_mask: GFP flags for the allocation
2587  *
2588  * Like alloc_pages_exact(), but try to allocate on node nid first before falling
2589  * back.
2590  * Note this is not alloc_pages_exact_node() which allocates on a specific node,
2591  * but is not exact.
2592  */
2593 void *alloc_pages_exact_nid(int nid, size_t size, gfp_t gfp_mask)
2594 {
2595         unsigned order = get_order(size);
2596         struct page *p = alloc_pages_node(nid, gfp_mask, order);
2597         if (!p)
2598                 return NULL;
2599         return make_alloc_exact((unsigned long)page_address(p), order, size);
2600 }
2601 EXPORT_SYMBOL(alloc_pages_exact_nid);
2602
2603 /**
2604  * free_pages_exact - release memory allocated via alloc_pages_exact()
2605  * @virt: the value returned by alloc_pages_exact.
2606  * @size: size of allocation, same value as passed to alloc_pages_exact().
2607  *
2608  * Release the memory allocated by a previous call to alloc_pages_exact.
2609  */
2610 void free_pages_exact(void *virt, size_t size)
2611 {
2612         unsigned long addr = (unsigned long)virt;
2613         unsigned long end = addr + PAGE_ALIGN(size);
2614
2615         while (addr < end) {
2616                 free_page(addr);
2617                 addr += PAGE_SIZE;
2618         }
2619 }
2620 EXPORT_SYMBOL(free_pages_exact);
2621
2622 static unsigned int nr_free_zone_pages(int offset)
2623 {
2624         struct zoneref *z;
2625         struct zone *zone;
2626
2627         /* Just pick one node, since fallback list is circular */
2628         unsigned int sum = 0;
2629
2630         struct zonelist *zonelist = node_zonelist(numa_node_id(), GFP_KERNEL);
2631
2632         for_each_zone_zonelist(zone, z, zonelist, offset) {
2633                 unsigned long size = zone->present_pages;
2634                 unsigned long high = high_wmark_pages(zone);
2635                 if (size > high)
2636                         sum += size - high;
2637         }
2638
2639         return sum;
2640 }
2641
2642 /*
2643  * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
2644  */
2645 unsigned int nr_free_buffer_pages(void)
2646 {
2647         return nr_free_zone_pages(gfp_zone(GFP_USER));
2648 }
2649 EXPORT_SYMBOL_GPL(nr_free_buffer_pages);
2650
2651 /*
2652  * Amount of free RAM allocatable within all zones
2653  */
2654 unsigned int nr_free_pagecache_pages(void)
2655 {
2656         return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
2657 }
2658
2659 static inline void show_node(struct zone *zone)
2660 {
2661         if (NUMA_BUILD)
2662                 printk("Node %d ", zone_to_nid(zone));
2663 }
2664
2665 void si_meminfo(struct sysinfo *val)
2666 {
2667         val->totalram = totalram_pages;
2668         val->sharedram = 0;
2669         val->freeram = global_page_state(NR_FREE_PAGES);
2670         val->bufferram = nr_blockdev_pages();
2671         val->totalhigh = totalhigh_pages;
2672         val->freehigh = nr_free_highpages();
2673         val->mem_unit = PAGE_SIZE;
2674 }
2675
2676 EXPORT_SYMBOL(si_meminfo);
2677
2678 #ifdef CONFIG_NUMA
2679 void si_meminfo_node(struct sysinfo *val, int nid)
2680 {
2681         pg_data_t *pgdat = NODE_DATA(nid);
2682
2683         val->totalram = pgdat->node_present_pages;
2684         val->freeram = node_page_state(nid, NR_FREE_PAGES);
2685 #ifdef CONFIG_HIGHMEM
2686         val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
2687         val->freehigh = zone_page_state(&pgdat->node_zones[ZONE_HIGHMEM],
2688                         NR_FREE_PAGES);
2689 #else
2690         val->totalhigh = 0;
2691         val->freehigh = 0;
2692 #endif
2693         val->mem_unit = PAGE_SIZE;
2694 }
2695 #endif
2696
2697 /*
2698  * Determine whether the node should be displayed or not, depending on whether
2699  * SHOW_MEM_FILTER_NODES was passed to show_free_areas().
2700  */
2701 bool skip_free_areas_node(unsigned int flags, int nid)
2702 {
2703         bool ret = false;
2704         unsigned int cpuset_mems_cookie;
2705
2706         if (!(flags & SHOW_MEM_FILTER_NODES))
2707                 goto out;
2708
2709         do {
2710                 cpuset_mems_cookie = get_mems_allowed();
2711                 ret = !node_isset(nid, cpuset_current_mems_allowed);
2712         } while (!put_mems_allowed(cpuset_mems_cookie));
2713 out:
2714         return ret;
2715 }
2716
2717 #define K(x) ((x) << (PAGE_SHIFT-10))
2718
2719 /*
2720  * Show free area list (used inside shift_scroll-lock stuff)
2721  * We also calculate the percentage fragmentation. We do this by counting the
2722  * memory on each free list with the exception of the first item on the list.
2723  * Suppresses nodes that are not allowed by current's cpuset if
2724  * SHOW_MEM_FILTER_NODES is passed.
2725  */
2726 void show_free_areas(unsigned int filter)
2727 {
2728         int cpu;
2729         struct zone *zone;
2730
2731         for_each_populated_zone(zone) {
2732                 if (skip_free_areas_node(filter, zone_to_nid(zone)))
2733                         continue;
2734                 show_node(zone);
2735                 printk("%s per-cpu:\n", zone->name);
2736
2737                 for_each_online_cpu(cpu) {
2738                         struct per_cpu_pageset *pageset;
2739
2740                         pageset = per_cpu_ptr(zone->pageset, cpu);
2741
2742                         printk("CPU %4d: hi:%5d, btch:%4d usd:%4d\n",
2743                                cpu, pageset->pcp.high,
2744                                pageset->pcp.batch, pageset->pcp.count);
2745                 }
2746         }
2747
2748         printk("active_anon:%lu inactive_anon:%lu isolated_anon:%lu\n"
2749                 " active_file:%lu inactive_file:%lu isolated_file:%lu\n"
2750                 " unevictable:%lu"
2751                 " dirty:%lu writeback:%lu unstable:%lu\n"
2752                 " free:%lu slab_reclaimable:%lu slab_unreclaimable:%lu\n"
2753                 " mapped:%lu shmem:%lu pagetables:%lu bounce:%lu\n",
2754                 global_page_state(NR_ACTIVE_ANON),
2755                 global_page_state(NR_INACTIVE_ANON),
2756                 global_page_state(NR_ISOLATED_ANON),
2757                 global_page_state(NR_ACTIVE_FILE),
2758                 global_page_state(NR_INACTIVE_FILE),
2759                 global_page_state(NR_ISOLATED_FILE),
2760                 global_page_state(NR_UNEVICTABLE),
2761                 global_page_state(NR_FILE_DIRTY),
2762                 global_page_state(NR_WRITEBACK),
2763                 global_page_state(NR_UNSTABLE_NFS),
2764                 global_page_state(NR_FREE_PAGES),
2765                 global_page_state(NR_SLAB_RECLAIMABLE),
2766                 global_page_state(NR_SLAB_UNRECLAIMABLE),
2767                 global_page_state(NR_FILE_MAPPED),
2768                 global_page_state(NR_SHMEM),
2769                 global_page_state(NR_PAGETABLE),
2770                 global_page_state(NR_BOUNCE));
2771
2772         for_each_populated_zone(zone) {
2773                 int i;
2774
2775                 if (skip_free_areas_node(filter, zone_to_nid(zone)))
2776                         continue;
2777                 show_node(zone);
2778                 printk("%s"
2779                         " free:%lukB"
2780                         " min:%lukB"
2781                         " low:%lukB"
2782                         " high:%lukB"
2783                         " active_anon:%lukB"
2784                         " inactive_anon:%lukB"
2785                         " active_file:%lukB"
2786                         " inactive_file:%lukB"
2787                         " unevictable:%lukB"
2788                         " isolated(anon):%lukB"
2789                         " isolated(file):%lukB"
2790                         " present:%lukB"
2791                         " mlocked:%lukB"
2792                         " dirty:%lukB"
2793                         " writeback:%lukB"
2794                         " mapped:%lukB"
2795                         " shmem:%lukB"
2796                         " slab_reclaimable:%lukB"
2797                         " slab_unreclaimable:%lukB"
2798                         " kernel_stack:%lukB"
2799                         " pagetables:%lukB"
2800                         " unstable:%lukB"
2801                         " bounce:%lukB"
2802                         " writeback_tmp:%lukB"
2803                         " pages_scanned:%lu"
2804                         " all_unreclaimable? %s"
2805                         "\n",
2806                         zone->name,
2807                         K(zone_page_state(zone, NR_FREE_PAGES)),
2808                         K(min_wmark_pages(zone)),
2809                         K(low_wmark_pages(zone)),
2810                         K(high_wmark_pages(zone)),
2811                         K(zone_page_state(zone, NR_ACTIVE_ANON)),
2812                         K(zone_page_state(zone, NR_INACTIVE_ANON)),
2813                         K(zone_page_state(zone, NR_ACTIVE_FILE)),
2814                         K(zone_page_state(zone, NR_INACTIVE_FILE)),
2815                         K(zone_page_state(zone, NR_UNEVICTABLE)),
2816                         K(zone_page_state(zone, NR_ISOLATED_ANON)),
2817                         K(zone_page_state(zone, NR_ISOLATED_FILE)),
2818                         K(zone->present_pages),
2819                         K(zone_page_state(zone, NR_MLOCK)),
2820                         K(zone_page_state(zone, NR_FILE_DIRTY)),
2821                         K(zone_page_state(zone, NR_WRITEBACK)),
2822                         K(zone_page_state(zone, NR_FILE_MAPPED)),
2823                         K(zone_page_state(zone, NR_SHMEM)),
2824                         K(zone_page_state(zone, NR_SLAB_RECLAIMABLE)),
2825                         K(zone_page_state(zone, NR_SLAB_UNRECLAIMABLE)),
2826                         zone_page_state(zone, NR_KERNEL_STACK) *
2827                                 THREAD_SIZE / 1024,
2828                         K(zone_page_state(zone, NR_PAGETABLE)),
2829                         K(zone_page_state(zone, NR_UNSTABLE_NFS)),
2830                         K(zone_page_state(zone, NR_BOUNCE)),
2831                         K(zone_page_state(zone, NR_WRITEBACK_TEMP)),
2832                         zone->pages_scanned,
2833                         (zone->all_unreclaimable ? "yes" : "no")
2834                         );
2835                 printk("lowmem_reserve[]:");
2836                 for (i = 0; i < MAX_NR_ZONES; i++)
2837                         printk(" %lu", zone->lowmem_reserve[i]);
2838                 printk("\n");
2839         }
2840
2841         for_each_populated_zone(zone) {
2842                 unsigned long nr[MAX_ORDER], flags, order, total = 0;
2843
2844                 if (skip_free_areas_node(filter, zone_to_nid(zone)))
2845                         continue;
2846                 show_node(zone);
2847                 printk("%s: ", zone->name);
2848
2849                 spin_lock_irqsave(&zone->lock, flags);
2850                 for (order = 0; order < MAX_ORDER; order++) {
2851                         nr[order] = zone->free_area[order].nr_free;
2852                         total += nr[order] << order;
2853                 }
2854                 spin_unlock_irqrestore(&zone->lock, flags);
2855                 for (order = 0; order < MAX_ORDER; order++)
2856                         printk("%lu*%lukB ", nr[order], K(1UL) << order);
2857                 printk("= %lukB\n", K(total));
2858         }
2859
2860         printk("%ld total pagecache pages\n", global_page_state(NR_FILE_PAGES));
2861
2862         show_swap_cache_info();
2863 }
2864
2865 static void zoneref_set_zone(struct zone *zone, struct zoneref *zoneref)
2866 {
2867         zoneref->zone = zone;
2868         zoneref->zone_idx = zone_idx(zone);
2869 }
2870
2871 /*
2872  * Builds allocation fallback zone lists.
2873  *
2874  * Add all populated zones of a node to the zonelist.
2875  */
2876 static int build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
2877                                 int nr_zones, enum zone_type zone_type)
2878 {
2879         struct zone *zone;
2880
2881         BUG_ON(zone_type >= MAX_NR_ZONES);
2882         zone_type++;
2883
2884         do {
2885                 zone_type--;
2886                 zone = pgdat->node_zones + zone_type;
2887                 if (populated_zone(zone)) {
2888                         zoneref_set_zone(zone,
2889                                 &zonelist->_zonerefs[nr_zones++]);
2890                         check_highest_zone(zone_type);
2891                 }
2892
2893         } while (zone_type);
2894         return nr_zones;
2895 }
2896
2897
2898 /*
2899  *  zonelist_order:
2900  *  0 = automatic detection of better ordering.
2901  *  1 = order by ([node] distance, -zonetype)
2902  *  2 = order by (-zonetype, [node] distance)
2903  *
2904  *  If not NUMA, ZONELIST_ORDER_ZONE and ZONELIST_ORDER_NODE will create
2905  *  the same zonelist. So only NUMA can configure this param.
2906  */
2907 #define ZONELIST_ORDER_DEFAULT  0
2908 #define ZONELIST_ORDER_NODE     1
2909 #define ZONELIST_ORDER_ZONE     2
2910
2911 /* zonelist order in the kernel.
2912  * set_zonelist_order() will set this to NODE or ZONE.
2913  */
2914 static int current_zonelist_order = ZONELIST_ORDER_DEFAULT;
2915 static char zonelist_order_name[3][8] = {"Default", "Node", "Zone"};
2916
2917
2918 #ifdef CONFIG_NUMA
2919 /* The value user specified ....changed by config */
2920 static int user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2921 /* string for sysctl */
2922 #define NUMA_ZONELIST_ORDER_LEN 16
2923 char numa_zonelist_order[16] = "default";
2924
2925 /*
2926  * interface for configure zonelist ordering.
2927  * command line option "numa_zonelist_order"
2928  *      = "[dD]efault   - default, automatic configuration.
2929  *      = "[nN]ode      - order by node locality, then by zone within node
2930  *      = "[zZ]one      - order by zone, then by locality within zone
2931  */
2932
2933 static int __parse_numa_zonelist_order(char *s)
2934 {
2935         if (*s == 'd' || *s == 'D') {
2936                 user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2937         } else if (*s == 'n' || *s == 'N') {
2938                 user_zonelist_order = ZONELIST_ORDER_NODE;
2939         } else if (*s == 'z' || *s == 'Z') {
2940                 user_zonelist_order = ZONELIST_ORDER_ZONE;
2941         } else {
2942                 printk(KERN_WARNING
2943                         "Ignoring invalid numa_zonelist_order value:  "
2944                         "%s\n", s);
2945                 return -EINVAL;
2946         }
2947         return 0;
2948 }
2949
2950 static __init int setup_numa_zonelist_order(char *s)
2951 {
2952         int ret;
2953
2954         if (!s)
2955                 return 0;
2956
2957         ret = __parse_numa_zonelist_order(s);
2958         if (ret == 0)
2959                 strlcpy(numa_zonelist_order, s, NUMA_ZONELIST_ORDER_LEN);
2960
2961         return ret;
2962 }
2963 early_param("numa_zonelist_order", setup_numa_zonelist_order);
2964
2965 /*
2966  * sysctl handler for numa_zonelist_order
2967  */
2968 int numa_zonelist_order_handler(ctl_table *table, int write,
2969                 void __user *buffer, size_t *length,
2970                 loff_t *ppos)
2971 {
2972         char saved_string[NUMA_ZONELIST_ORDER_LEN];
2973         int ret;
2974         static DEFINE_MUTEX(zl_order_mutex);
2975
2976         mutex_lock(&zl_order_mutex);
2977         if (write)
2978                 strcpy(saved_string, (char*)table->data);
2979         ret = proc_dostring(table, write, buffer, length, ppos);
2980         if (ret)
2981                 goto out;
2982         if (write) {
2983                 int oldval = user_zonelist_order;
2984                 if (__parse_numa_zonelist_order((char*)table->data)) {
2985                         /*
2986                          * bogus value.  restore saved string
2987                          */
2988                         strncpy((char*)table->data, saved_string,
2989                                 NUMA_ZONELIST_ORDER_LEN);
2990                         user_zonelist_order = oldval;
2991                 } else if (oldval != user_zonelist_order) {
2992                         mutex_lock(&zonelists_mutex);
2993                         build_all_zonelists(NULL);
2994                         mutex_unlock(&zonelists_mutex);
2995                 }
2996         }
2997 out:
2998         mutex_unlock(&zl_order_mutex);
2999         return ret;
3000 }
3001
3002
3003 #define MAX_NODE_LOAD (nr_online_nodes)
3004 static int node_load[MAX_NUMNODES];
3005
3006 /**
3007  * find_next_best_node - find the next node that should appear in a given node's fallback list
3008  * @node: node whose fallback list we're appending
3009  * @used_node_mask: nodemask_t of already used nodes
3010  *
3011  * We use a number of factors to determine which is the next node that should
3012  * appear on a given node's fallback list.  The node should not have appeared
3013  * already in @node's fallback list, and it should be the next closest node
3014  * according to the distance array (which contains arbitrary distance values
3015  * from each node to each node in the system), and should also prefer nodes
3016  * with no CPUs, since presumably they'll have very little allocation pressure
3017  * on them otherwise.
3018  * It returns -1 if no node is found.
3019  */
3020 static int find_next_best_node(int node, nodemask_t *used_node_mask)
3021 {
3022         int n, val;
3023         int min_val = INT_MAX;
3024         int best_node = -1;
3025         const struct cpumask *tmp = cpumask_of_node(0);
3026
3027         /* Use the local node if we haven't already */
3028         if (!node_isset(node, *used_node_mask)) {
3029                 node_set(node, *used_node_mask);
3030                 return node;
3031         }
3032
3033         for_each_node_state(n, N_HIGH_MEMORY) {
3034
3035                 /* Don't want a node to appear more than once */
3036                 if (node_isset(n, *used_node_mask))
3037                         continue;
3038
3039                 /* Use the distance array to find the distance */
3040                 val = node_distance(node, n);
3041
3042                 /* Penalize nodes under us ("prefer the next node") */
3043                 val += (n < node);
3044
3045                 /* Give preference to headless and unused nodes */
3046                 tmp = cpumask_of_node(n);
3047                 if (!cpumask_empty(tmp))
3048                         val += PENALTY_FOR_NODE_WITH_CPUS;
3049
3050                 /* Slight preference for less loaded node */
3051                 val *= (MAX_NODE_LOAD*MAX_NUMNODES);
3052                 val += node_load[n];
3053
3054                 if (val < min_val) {
3055                         min_val = val;
3056                         best_node = n;
3057                 }
3058         }
3059
3060         if (best_node >= 0)
3061                 node_set(best_node, *used_node_mask);
3062
3063         return best_node;
3064 }
3065
3066
3067 /*
3068  * Build zonelists ordered by node and zones within node.
3069  * This results in maximum locality--normal zone overflows into local
3070  * DMA zone, if any--but risks exhausting DMA zone.
3071  */
3072 static void build_zonelists_in_node_order(pg_data_t *pgdat, int node)
3073 {
3074         int j;
3075         struct zonelist *zonelist;
3076
3077         zonelist = &pgdat->node_zonelists[0];
3078         for (j = 0; zonelist->_zonerefs[j].zone != NULL; j++)
3079                 ;
3080         j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3081                                                         MAX_NR_ZONES - 1);
3082         zonelist->_zonerefs[j].zone = NULL;
3083         zonelist->_zonerefs[j].zone_idx = 0;
3084 }
3085
3086 /*
3087  * Build gfp_thisnode zonelists
3088  */
3089 static void build_thisnode_zonelists(pg_data_t *pgdat)
3090 {
3091         int j;
3092         struct zonelist *zonelist;
3093
3094         zonelist = &pgdat->node_zonelists[1];
3095         j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
3096         zonelist->_zonerefs[j].zone = NULL;
3097         zonelist->_zonerefs[j].zone_idx = 0;
3098 }
3099
3100 /*
3101  * Build zonelists ordered by zone and nodes within zones.
3102  * This results in conserving DMA zone[s] until all Normal memory is
3103  * exhausted, but results in overflowing to remote node while memory
3104  * may still exist in local DMA zone.
3105  */
3106 static int node_order[MAX_NUMNODES];
3107
3108 static void build_zonelists_in_zone_order(pg_data_t *pgdat, int nr_nodes)
3109 {
3110         int pos, j, node;
3111         int zone_type;          /* needs to be signed */
3112         struct zone *z;
3113         struct zonelist *zonelist;
3114
3115         zonelist = &pgdat->node_zonelists[0];
3116         pos = 0;
3117         for (zone_type = MAX_NR_ZONES - 1; zone_type >= 0; zone_type--) {
3118                 for (j = 0; j < nr_nodes; j++) {
3119                         node = node_order[j];
3120                         z = &NODE_DATA(node)->node_zones[zone_type];
3121                         if (populated_zone(z)) {
3122                                 zoneref_set_zone(z,
3123                                         &zonelist->_zonerefs[pos++]);
3124                                 check_highest_zone(zone_type);
3125                         }
3126                 }
3127         }
3128         zonelist->_zonerefs[pos].zone = NULL;
3129         zonelist->_zonerefs[pos].zone_idx = 0;
3130 }
3131
3132 static int default_zonelist_order(void)
3133 {
3134         int nid, zone_type;
3135         unsigned long low_kmem_size,total_size;
3136         struct zone *z;
3137         int average_size;
3138         /*
3139          * ZONE_DMA and ZONE_DMA32 can be very small area in the system.
3140          * If they are really small and used heavily, the system can fall
3141          * into OOM very easily.
3142          * This function detect ZONE_DMA/DMA32 size and configures zone order.
3143          */
3144         /* Is there ZONE_NORMAL ? (ex. ppc has only DMA zone..) */
3145         low_kmem_size = 0;
3146         total_size = 0;
3147         for_each_online_node(nid) {
3148                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
3149                         z = &NODE_DATA(nid)->node_zones[zone_type];
3150                         if (populated_zone(z)) {
3151                                 if (zone_type < ZONE_NORMAL)
3152                                         low_kmem_size += z->present_pages;
3153                                 total_size += z->present_pages;
3154                         } else if (zone_type == ZONE_NORMAL) {
3155                                 /*
3156                                  * If any node has only lowmem, then node order
3157                                  * is preferred to allow kernel allocations
3158                                  * locally; otherwise, they can easily infringe
3159                                  * on other nodes when there is an abundance of
3160                                  * lowmem available to allocate from.
3161                                  */
3162                                 return ZONELIST_ORDER_NODE;
3163                         }
3164                 }
3165         }
3166         if (!low_kmem_size ||  /* there are no DMA area. */
3167             low_kmem_size > total_size/2) /* DMA/DMA32 is big. */
3168                 return ZONELIST_ORDER_NODE;
3169         /*
3170          * look into each node's config.
3171          * If there is a node whose DMA/DMA32 memory is very big area on
3172          * local memory, NODE_ORDER may be suitable.
3173          */
3174         average_size = total_size /
3175                                 (nodes_weight(node_states[N_HIGH_MEMORY]) + 1);
3176         for_each_online_node(nid) {
3177                 low_kmem_size = 0;
3178                 total_size = 0;
3179                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
3180                         z = &NODE_DATA(nid)->node_zones[zone_type];
3181                         if (populated_zone(z)) {
3182                                 if (zone_type < ZONE_NORMAL)
3183                                         low_kmem_size += z->present_pages;
3184                                 total_size += z->present_pages;
3185                         }
3186                 }
3187                 if (low_kmem_size &&
3188                     total_size > average_size && /* ignore small node */
3189                     low_kmem_size > total_size * 70/100)
3190                         return ZONELIST_ORDER_NODE;
3191         }
3192         return ZONELIST_ORDER_ZONE;
3193 }
3194
3195 static void set_zonelist_order(void)
3196 {
3197         if (user_zonelist_order == ZONELIST_ORDER_DEFAULT)
3198                 current_zonelist_order = default_zonelist_order();
3199         else
3200                 current_zonelist_order = user_zonelist_order;
3201 }
3202
3203 static void build_zonelists(pg_data_t *pgdat)
3204 {
3205         int j, node, load;
3206         enum zone_type i;
3207         nodemask_t used_mask;
3208         int local_node, prev_node;
3209         struct zonelist *zonelist;
3210         int order = current_zonelist_order;
3211
3212         /* initialize zonelists */
3213         for (i = 0; i < MAX_ZONELISTS; i++) {
3214                 zonelist = pgdat->node_zonelists + i;
3215                 zonelist->_zonerefs[0].zone = NULL;
3216                 zonelist->_zonerefs[0].zone_idx = 0;
3217         }
3218
3219         /* NUMA-aware ordering of nodes */
3220         local_node = pgdat->node_id;
3221         load = nr_online_nodes;
3222         prev_node = local_node;
3223         nodes_clear(used_mask);
3224
3225         memset(node_order, 0, sizeof(node_order));
3226         j = 0;
3227
3228         while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
3229                 int distance = node_distance(local_node, node);
3230
3231                 /*
3232                  * If another node is sufficiently far away then it is better
3233                  * to reclaim pages in a zone before going off node.
3234                  */
3235                 if (distance > RECLAIM_DISTANCE)
3236                         zone_reclaim_mode = 1;
3237
3238                 /*
3239                  * We don't want to pressure a particular node.
3240                  * So adding penalty to the first node in same
3241                  * distance group to make it round-robin.
3242                  */
3243                 if (distance != node_distance(local_node, prev_node))
3244                         node_load[node] = load;
3245
3246                 prev_node = node;
3247                 load--;
3248                 if (order == ZONELIST_ORDER_NODE)
3249                         build_zonelists_in_node_order(pgdat, node);
3250                 else
3251                         node_order[j++] = node; /* remember order */
3252         }
3253
3254         if (order == ZONELIST_ORDER_ZONE) {
3255                 /* calculate node order -- i.e., DMA last! */
3256                 build_zonelists_in_zone_order(pgdat, j);
3257         }
3258
3259         build_thisnode_zonelists(pgdat);
3260 }
3261
3262 /* Construct the zonelist performance cache - see further mmzone.h */
3263 static void build_zonelist_cache(pg_data_t *pgdat)
3264 {
3265         struct zonelist *zonelist;
3266         struct zonelist_cache *zlc;
3267         struct zoneref *z;
3268
3269         zonelist = &pgdat->node_zonelists[0];
3270         zonelist->zlcache_ptr = zlc = &zonelist->zlcache;
3271         bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
3272         for (z = zonelist->_zonerefs; z->zone; z++)
3273                 zlc->z_to_n[z - zonelist->_zonerefs] = zonelist_node_idx(z);
3274 }
3275
3276 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
3277 /*
3278  * Return node id of node used for "local" allocations.
3279  * I.e., first node id of first zone in arg node's generic zonelist.
3280  * Used for initializing percpu 'numa_mem', which is used primarily
3281  * for kernel allocations, so use GFP_KERNEL flags to locate zonelist.
3282  */
3283 int local_memory_node(int node)
3284 {
3285         struct zone *zone;
3286
3287         (void)first_zones_zonelist(node_zonelist(node, GFP_KERNEL),
3288                                    gfp_zone(GFP_KERNEL),
3289                                    NULL,
3290                                    &zone);
3291         return zone->node;
3292 }
3293 #endif
3294
3295 #else   /* CONFIG_NUMA */
3296
3297 static void set_zonelist_order(void)
3298 {
3299         current_zonelist_order = ZONELIST_ORDER_ZONE;
3300 }
3301
3302 static void build_zonelists(pg_data_t *pgdat)
3303 {
3304         int node, local_node;
3305         enum zone_type j;
3306         struct zonelist *zonelist;
3307
3308         local_node = pgdat->node_id;
3309
3310         zonelist = &pgdat->node_zonelists[0];
3311         j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
3312
3313         /*
3314          * Now we build the zonelist so that it contains the zones
3315          * of all the other nodes.
3316          * We don't want to pressure a particular node, so when
3317          * building the zones for node N, we make sure that the
3318          * zones coming right after the local ones are those from
3319          * node N+1 (modulo N)
3320          */
3321         for (node = local_node + 1; node < MAX_NUMNODES; node++) {
3322                 if (!node_online(node))
3323                         continue;
3324                 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3325                                                         MAX_NR_ZONES - 1);
3326         }
3327         for (node = 0; node < local_node; node++) {
3328                 if (!node_online(node))
3329                         continue;
3330                 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3331                                                         MAX_NR_ZONES - 1);
3332         }
3333
3334         zonelist->_zonerefs[j].zone = NULL;
3335         zonelist->_zonerefs[j].zone_idx = 0;
3336 }
3337
3338 /* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
3339 static void build_zonelist_cache(pg_data_t *pgdat)
3340 {
3341         pgdat->node_zonelists[0].zlcache_ptr = NULL;
3342 }
3343
3344 #endif  /* CONFIG_NUMA */
3345
3346 /*
3347  * Boot pageset table. One per cpu which is going to be used for all
3348  * zones and all nodes. The parameters will be set in such a way
3349  * that an item put on a list will immediately be handed over to
3350  * the buddy list. This is safe since pageset manipulation is done
3351  * with interrupts disabled.
3352  *
3353  * The boot_pagesets must be kept even after bootup is complete for
3354  * unused processors and/or zones. They do play a role for bootstrapping
3355  * hotplugged processors.
3356  *
3357  * zoneinfo_show() and maybe other functions do
3358  * not check if the processor is online before following the pageset pointer.
3359  * Other parts of the kernel may not check if the zone is available.
3360  */
3361 static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch);
3362 static DEFINE_PER_CPU(struct per_cpu_pageset, boot_pageset);
3363 static void setup_zone_pageset(struct zone *zone);
3364
3365 /*
3366  * Global mutex to protect against size modification of zonelists
3367  * as well as to serialize pageset setup for the new populated zone.
3368  */
3369 DEFINE_MUTEX(zonelists_mutex);
3370
3371 /* return values int ....just for stop_machine() */
3372 static __init_refok int __build_all_zonelists(void *data)
3373 {
3374         int nid;
3375         int cpu;
3376
3377 #ifdef CONFIG_NUMA
3378         memset(node_load, 0, sizeof(node_load));
3379 #endif
3380         for_each_online_node(nid) {
3381                 pg_data_t *pgdat = NODE_DATA(nid);
3382
3383                 build_zonelists(pgdat);
3384                 build_zonelist_cache(pgdat);
3385         }
3386
3387         /*
3388          * Initialize the boot_pagesets that are going to be used
3389          * for bootstrapping processors. The real pagesets for
3390          * each zone will be allocated later when the per cpu
3391          * allocator is available.
3392          *
3393          * boot_pagesets are used also for bootstrapping offline
3394          * cpus if the system is already booted because the pagesets
3395          * are needed to initialize allocators on a specific cpu too.
3396          * F.e. the percpu allocator needs the page allocator which
3397          * needs the percpu allocator in order to allocate its pagesets
3398          * (a chicken-egg dilemma).
3399          */
3400         for_each_possible_cpu(cpu) {
3401                 setup_pageset(&per_cpu(boot_pageset, cpu), 0);
3402
3403 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
3404                 /*
3405                  * We now know the "local memory node" for each node--
3406                  * i.e., the node of the first zone in the generic zonelist.
3407                  * Set up numa_mem percpu variable for on-line cpus.  During