linux/mm/page_alloc.c
<<
>>
Prefs
   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/oom.h>
  34#include <linux/notifier.h>
  35#include <linux/topology.h>
  36#include <linux/sysctl.h>
  37#include <linux/cpu.h>
  38#include <linux/cpuset.h>
  39#include <linux/memory_hotplug.h>
  40#include <linux/nodemask.h>
  41#include <linux/vmalloc.h>
  42#include <linux/mempolicy.h>
  43#include <linux/stop_machine.h>
  44#include <linux/sort.h>
  45#include <linux/pfn.h>
  46#include <linux/backing-dev.h>
  47#include <linux/fault-inject.h>
  48#include <linux/page-isolation.h>
  49#include <linux/page_cgroup.h>
  50#include <linux/debugobjects.h>
  51#include <linux/kmemleak.h>
  52#include <linux/memory.h>
  53#include <linux/compaction.h>
  54#include <trace/events/kmem.h>
  55#include <linux/ftrace_event.h>
  56#include <linux/memcontrol.h>
  57
  58#include <asm/tlbflush.h>
  59#include <asm/div64.h>
  60#include "internal.h"
  61
  62#ifdef CONFIG_USE_PERCPU_NUMA_NODE_ID
  63DEFINE_PER_CPU(int, numa_node);
  64EXPORT_PER_CPU_SYMBOL(numa_node);
  65#endif
  66
  67#ifdef CONFIG_HAVE_MEMORYLESS_NODES
  68/*
  69 * N.B., Do NOT reference the '_numa_mem_' per cpu variable directly.
  70 * It will not be defined when CONFIG_HAVE_MEMORYLESS_NODES is not defined.
  71 * Use the accessor functions set_numa_mem(), numa_mem_id() and cpu_to_mem()
  72 * defined in <linux/topology.h>.
  73 */
  74DEFINE_PER_CPU(int, _numa_mem_);                /* Kernel "local memory" node */
  75EXPORT_PER_CPU_SYMBOL(_numa_mem_);
  76#endif
  77
  78/*
  79 * Array of node states.
  80 */
  81nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
  82        [N_POSSIBLE] = NODE_MASK_ALL,
  83        [N_ONLINE] = { { [0] = 1UL } },
  84#ifndef CONFIG_NUMA
  85        [N_NORMAL_MEMORY] = { { [0] = 1UL } },
  86#ifdef CONFIG_HIGHMEM
  87        [N_HIGH_MEMORY] = { { [0] = 1UL } },
  88#endif
  89        [N_CPU] = { { [0] = 1UL } },
  90#endif  /* NUMA */
  91};
  92EXPORT_SYMBOL(node_states);
  93
  94unsigned long totalram_pages __read_mostly;
  95unsigned long totalreserve_pages __read_mostly;
  96int percpu_pagelist_fraction;
  97gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
  98
  99#ifdef CONFIG_PM_SLEEP
 100/*
 101 * The following functions are used by the suspend/hibernate code to temporarily
 102 * change gfp_allowed_mask in order to avoid using I/O during memory allocations
 103 * while devices are suspended.  To avoid races with the suspend/hibernate code,
 104 * they should always be called with pm_mutex held (gfp_allowed_mask also should
 105 * only be modified with pm_mutex held, unless the suspend/hibernate code is
 106 * guaranteed not to run in parallel with that modification).
 107 */
 108
 109static gfp_t saved_gfp_mask;
 110
 111void pm_restore_gfp_mask(void)
 112{
 113        WARN_ON(!mutex_is_locked(&pm_mutex));
 114        if (saved_gfp_mask) {
 115                gfp_allowed_mask = saved_gfp_mask;
 116                saved_gfp_mask = 0;
 117        }
 118}
 119
 120void pm_restrict_gfp_mask(void)
 121{
 122        WARN_ON(!mutex_is_locked(&pm_mutex));
 123        WARN_ON(saved_gfp_mask);
 124        saved_gfp_mask = gfp_allowed_mask;
 125        gfp_allowed_mask &= ~GFP_IOFS;
 126}
 127#endif /* CONFIG_PM_SLEEP */
 128
 129#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
 130int pageblock_order __read_mostly;
 131#endif
 132
 133static void __free_pages_ok(struct page *page, unsigned int order);
 134
 135/*
 136 * results with 256, 32 in the lowmem_reserve sysctl:
 137 *      1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
 138 *      1G machine -> (16M dma, 784M normal, 224M high)
 139 *      NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
 140 *      HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
 141 *      HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
 142 *
 143 * TBD: should special case ZONE_DMA32 machines here - in those we normally
 144 * don't need any ZONE_NORMAL reservation
 145 */
 146int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
 147#ifdef CONFIG_ZONE_DMA
 148         256,
 149#endif
 150#ifdef CONFIG_ZONE_DMA32
 151         256,
 152#endif
 153#ifdef CONFIG_HIGHMEM
 154         32,
 155#endif
 156         32,
 157};
 158
 159EXPORT_SYMBOL(totalram_pages);
 160
 161static char * const zone_names[MAX_NR_ZONES] = {
 162#ifdef CONFIG_ZONE_DMA
 163         "DMA",
 164#endif
 165#ifdef CONFIG_ZONE_DMA32
 166         "DMA32",
 167#endif
 168         "Normal",
 169#ifdef CONFIG_HIGHMEM
 170         "HighMem",
 171#endif
 172         "Movable",
 173};
 174
 175int min_free_kbytes = 1024;
 176
 177static unsigned long __meminitdata nr_kernel_pages;
 178static unsigned long __meminitdata nr_all_pages;
 179static unsigned long __meminitdata dma_reserve;
 180
 181#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
 182  /*
 183   * MAX_ACTIVE_REGIONS determines the maximum number of distinct
 184   * ranges of memory (RAM) that may be registered with add_active_range().
 185   * Ranges passed to add_active_range() will be merged if possible
 186   * so the number of times add_active_range() can be called is
 187   * related to the number of nodes and the number of holes
 188   */
 189  #ifdef CONFIG_MAX_ACTIVE_REGIONS
 190    /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */
 191    #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS
 192  #else
 193    #if MAX_NUMNODES >= 32
 194      /* If there can be many nodes, allow up to 50 holes per node */
 195      #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50)
 196    #else
 197      /* By default, allow up to 256 distinct regions */
 198      #define MAX_ACTIVE_REGIONS 256
 199    #endif
 200  #endif
 201
 202  static struct node_active_region __meminitdata early_node_map[MAX_ACTIVE_REGIONS];
 203  static int __meminitdata nr_nodemap_entries;
 204  static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
 205  static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
 206  static unsigned long __initdata required_kernelcore;
 207  static unsigned long __initdata required_movablecore;
 208  static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
 209
 210  /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
 211  int movable_zone;
 212  EXPORT_SYMBOL(movable_zone);
 213#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
 214
 215#if MAX_NUMNODES > 1
 216int nr_node_ids __read_mostly = MAX_NUMNODES;
 217int nr_online_nodes __read_mostly = 1;
 218EXPORT_SYMBOL(nr_node_ids);
 219EXPORT_SYMBOL(nr_online_nodes);
 220#endif
 221
 222int page_group_by_mobility_disabled __read_mostly;
 223
 224static void set_pageblock_migratetype(struct page *page, int migratetype)
 225{
 226
 227        if (unlikely(page_group_by_mobility_disabled))
 228                migratetype = MIGRATE_UNMOVABLE;
 229
 230        set_pageblock_flags_group(page, (unsigned long)migratetype,
 231                                        PB_migrate, PB_migrate_end);
 232}
 233
 234bool oom_killer_disabled __read_mostly;
 235
 236#ifdef CONFIG_DEBUG_VM
 237static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
 238{
 239        int ret = 0;
 240        unsigned seq;
 241        unsigned long pfn = page_to_pfn(page);
 242
 243        do {
 244                seq = zone_span_seqbegin(zone);
 245                if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
 246                        ret = 1;
 247                else if (pfn < zone->zone_start_pfn)
 248                        ret = 1;
 249        } while (zone_span_seqretry(zone, seq));
 250
 251        return ret;
 252}
 253
 254static int page_is_consistent(struct zone *zone, struct page *page)
 255{
 256        if (!pfn_valid_within(page_to_pfn(page)))
 257                return 0;
 258        if (zone != page_zone(page))
 259                return 0;
 260
 261        return 1;
 262}
 263/*
 264 * Temporary debugging check for pages not lying within a given zone.
 265 */
 266static int bad_range(struct zone *zone, struct page *page)
 267{
 268        if (page_outside_zone_boundaries(zone, page))
 269                return 1;
 270        if (!page_is_consistent(zone, page))
 271                return 1;
 272
 273        return 0;
 274}
 275#else
 276static inline int bad_range(struct zone *zone, struct page *page)
 277{
 278        return 0;
 279}
 280#endif
 281
 282static void bad_page(struct page *page)
 283{
 284        static unsigned long resume;
 285        static unsigned long nr_shown;
 286        static unsigned long nr_unshown;
 287
 288        /* Don't complain about poisoned pages */
 289        if (PageHWPoison(page)) {
 290                reset_page_mapcount(page); /* remove PageBuddy */
 291                return;
 292        }
 293
 294        /*
 295         * Allow a burst of 60 reports, then keep quiet for that minute;
 296         * or allow a steady drip of one report per second.
 297         */
 298        if (nr_shown == 60) {
 299                if (time_before(jiffies, resume)) {
 300                        nr_unshown++;
 301                        goto out;
 302                }
 303                if (nr_unshown) {
 304                        printk(KERN_ALERT
 305                              "BUG: Bad page state: %lu messages suppressed\n",
 306                                nr_unshown);
 307                        nr_unshown = 0;
 308                }
 309                nr_shown = 0;
 310        }
 311        if (nr_shown++ == 0)
 312                resume = jiffies + 60 * HZ;
 313
 314        printk(KERN_ALERT "BUG: Bad page state in process %s  pfn:%05lx\n",
 315                current->comm, page_to_pfn(page));
 316        dump_page(page);
 317
 318        dump_stack();
 319out:
 320        /* Leave bad fields for debug, except PageBuddy could make trouble */
 321        reset_page_mapcount(page); /* remove PageBuddy */
 322        add_taint(TAINT_BAD_PAGE);
 323}
 324
 325/*
 326 * Higher-order pages are called "compound pages".  They are structured thusly:
 327 *
 328 * The first PAGE_SIZE page is called the "head page".
 329 *
 330 * The remaining PAGE_SIZE pages are called "tail pages".
 331 *
 332 * All pages have PG_compound set.  All pages have their ->private pointing at
 333 * the head page (even the head page has this).
 334 *
 335 * The first tail page's ->lru.next holds the address of the compound page's
 336 * put_page() function.  Its ->lru.prev holds the order of allocation.
 337 * This usage means that zero-order pages may not be compound.
 338 */
 339
 340static void free_compound_page(struct page *page)
 341{
 342        __free_pages_ok(page, compound_order(page));
 343}
 344
 345void prep_compound_page(struct page *page, unsigned long order)
 346{
 347        int i;
 348        int nr_pages = 1 << order;
 349
 350        set_compound_page_dtor(page, free_compound_page);
 351        set_compound_order(page, order);
 352        __SetPageHead(page);
 353        for (i = 1; i < nr_pages; i++) {
 354                struct page *p = page + i;
 355
 356                __SetPageTail(p);
 357                p->first_page = page;
 358        }
 359}
 360
 361/* update __split_huge_page_refcount if you change this function */
 362static int destroy_compound_page(struct page *page, unsigned long order)
 363{
 364        int i;
 365        int nr_pages = 1 << order;
 366        int bad = 0;
 367
 368        if (unlikely(compound_order(page) != order) ||
 369            unlikely(!PageHead(page))) {
 370                bad_page(page);
 371                bad++;
 372        }
 373
 374        __ClearPageHead(page);
 375
 376        for (i = 1; i < nr_pages; i++) {
 377                struct page *p = page + i;
 378
 379                if (unlikely(!PageTail(p) || (p->first_page != page))) {
 380                        bad_page(page);
 381                        bad++;
 382                }
 383                __ClearPageTail(p);
 384        }
 385
 386        return bad;
 387}
 388
 389static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
 390{
 391        int i;
 392
 393        /*
 394         * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
 395         * and __GFP_HIGHMEM from hard or soft interrupt context.
 396         */
 397        VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
 398        for (i = 0; i < (1 << order); i++)
 399                clear_highpage(page + i);
 400}
 401
 402static inline void set_page_order(struct page *page, int order)
 403{
 404        set_page_private(page, order);
 405        __SetPageBuddy(page);
 406}
 407
 408static inline void rmv_page_order(struct page *page)
 409{
 410        __ClearPageBuddy(page);
 411        set_page_private(page, 0);
 412}
 413
 414/*
 415 * Locate the struct page for both the matching buddy in our
 416 * pair (buddy1) and the combined O(n+1) page they form (page).
 417 *
 418 * 1) Any buddy B1 will have an order O twin B2 which satisfies
 419 * the following equation:
 420 *     B2 = B1 ^ (1 << O)
 421 * For example, if the starting buddy (buddy2) is #8 its order
 422 * 1 buddy is #10:
 423 *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
 424 *
 425 * 2) Any buddy B will have an order O+1 parent P which
 426 * satisfies the following equation:
 427 *     P = B & ~(1 << O)
 428 *
 429 * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
 430 */
 431static inline unsigned long
 432__find_buddy_index(unsigned long page_idx, unsigned int order)
 433{
 434        return page_idx ^ (1 << order);
 435}
 436
 437/*
 438 * This function checks whether a page is free && is the buddy
 439 * we can do coalesce a page and its buddy if
 440 * (a) the buddy is not in a hole &&
 441 * (b) the buddy is in the buddy system &&
 442 * (c) a page and its buddy have the same order &&
 443 * (d) a page and its buddy are in the same zone.
 444 *
 445 * For recording whether a page is in the buddy system, we set ->_mapcount -2.
 446 * Setting, clearing, and testing _mapcount -2 is serialized by zone->lock.
 447 *
 448 * For recording page's order, we use page_private(page).
 449 */
 450static inline int page_is_buddy(struct page *page, struct page *buddy,
 451                                                                int order)
 452{
 453        if (!pfn_valid_within(page_to_pfn(buddy)))
 454                return 0;
 455
 456        if (page_zone_id(page) != page_zone_id(buddy))
 457                return 0;
 458
 459        if (PageBuddy(buddy) && page_order(buddy) == order) {
 460                VM_BUG_ON(page_count(buddy) != 0);
 461                return 1;
 462        }
 463        return 0;
 464}
 465
 466/*
 467 * Freeing function for a buddy system allocator.
 468 *
 469 * The concept of a buddy system is to maintain direct-mapped table
 470 * (containing bit values) for memory blocks of various "orders".
 471 * The bottom level table contains the map for the smallest allocatable
 472 * units of memory (here, pages), and each level above it describes
 473 * pairs of units from the levels below, hence, "buddies".
 474 * At a high level, all that happens here is marking the table entry
 475 * at the bottom level available, and propagating the changes upward
 476 * as necessary, plus some accounting needed to play nicely with other
 477 * parts of the VM system.
 478 * At each level, we keep a list of pages, which are heads of continuous
 479 * free pages of length of (1 << order) and marked with _mapcount -2. Page's
 480 * order is recorded in page_private(page) field.
 481 * So when we are allocating or freeing one, we can derive the state of the
 482 * other.  That is, if we allocate a small block, and both were   
 483 * free, the remainder of the region must be split into blocks.   
 484 * If a block is freed, and its buddy is also free, then this
 485 * triggers coalescing into a block of larger size.            
 486 *
 487 * -- wli
 488 */
 489
 490static inline void __free_one_page(struct page *page,
 491                struct zone *zone, unsigned int order,
 492                int migratetype)
 493{
 494        unsigned long page_idx;
 495        unsigned long combined_idx;
 496        unsigned long uninitialized_var(buddy_idx);
 497        struct page *buddy;
 498
 499        if (unlikely(PageCompound(page)))
 500                if (unlikely(destroy_compound_page(page, order)))
 501                        return;
 502
 503        VM_BUG_ON(migratetype == -1);
 504
 505        page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
 506
 507        VM_BUG_ON(page_idx & ((1 << order) - 1));
 508        VM_BUG_ON(bad_range(zone, page));
 509
 510        while (order < MAX_ORDER-1) {
 511                buddy_idx = __find_buddy_index(page_idx, order);
 512                buddy = page + (buddy_idx - page_idx);
 513                if (!page_is_buddy(page, buddy, order))
 514                        break;
 515
 516                /* Our buddy is free, merge with it and move up one order. */
 517                list_del(&buddy->lru);
 518                zone->free_area[order].nr_free--;
 519                rmv_page_order(buddy);
 520                combined_idx = buddy_idx & page_idx;
 521                page = page + (combined_idx - page_idx);
 522                page_idx = combined_idx;
 523                order++;
 524        }
 525        set_page_order(page, order);
 526
 527        /*
 528         * If this is not the largest possible page, check if the buddy
 529         * of the next-highest order is free. If it is, it's possible
 530         * that pages are being freed that will coalesce soon. In case,
 531         * that is happening, add the free page to the tail of the list
 532         * so it's less likely to be used soon and more likely to be merged
 533         * as a higher order page
 534         */
 535        if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
 536                struct page *higher_page, *higher_buddy;
 537                combined_idx = buddy_idx & page_idx;
 538                higher_page = page + (combined_idx - page_idx);
 539                buddy_idx = __find_buddy_index(combined_idx, order + 1);
 540                higher_buddy = page + (buddy_idx - combined_idx);
 541                if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
 542                        list_add_tail(&page->lru,
 543                                &zone->free_area[order].free_list[migratetype]);
 544                        goto out;
 545                }
 546        }
 547
 548        list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
 549out:
 550        zone->free_area[order].nr_free++;
 551}
 552
 553/*
 554 * free_page_mlock() -- clean up attempts to free and mlocked() page.
 555 * Page should not be on lru, so no need to fix that up.
 556 * free_pages_check() will verify...
 557 */
 558static inline void free_page_mlock(struct page *page)
 559{
 560        __dec_zone_page_state(page, NR_MLOCK);
 561        __count_vm_event(UNEVICTABLE_MLOCKFREED);
 562}
 563
 564static inline int free_pages_check(struct page *page)
 565{
 566        if (unlikely(page_mapcount(page) |
 567                (page->mapping != NULL)  |
 568                (atomic_read(&page->_count) != 0) |
 569                (page->flags & PAGE_FLAGS_CHECK_AT_FREE) |
 570                (mem_cgroup_bad_page_check(page)))) {
 571                bad_page(page);
 572                return 1;
 573        }
 574        if (page->flags & PAGE_FLAGS_CHECK_AT_PREP)
 575                page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
 576        return 0;
 577}
 578
 579/*
 580 * Frees a number of pages from the PCP lists
 581 * Assumes all pages on list are in same zone, and of same order.
 582 * count is the number of pages to free.
 583 *
 584 * If the zone was previously in an "all pages pinned" state then look to
 585 * see if this freeing clears that state.
 586 *
 587 * And clear the zone's pages_scanned counter, to hold off the "all pages are
 588 * pinned" detection logic.
 589 */
 590static void free_pcppages_bulk(struct zone *zone, int count,
 591                                        struct per_cpu_pages *pcp)
 592{
 593        int migratetype = 0;
 594        int batch_free = 0;
 595        int to_free = count;
 596
 597        spin_lock(&zone->lock);
 598        zone->all_unreclaimable = 0;
 599        zone->pages_scanned = 0;
 600
 601        while (to_free) {
 602                struct page *page;
 603                struct list_head *list;
 604
 605                /*
 606                 * Remove pages from lists in a round-robin fashion. A
 607                 * batch_free count is maintained that is incremented when an
 608                 * empty list is encountered.  This is so more pages are freed
 609                 * off fuller lists instead of spinning excessively around empty
 610                 * lists
 611                 */
 612                do {
 613                        batch_free++;
 614                        if (++migratetype == MIGRATE_PCPTYPES)
 615                                migratetype = 0;
 616                        list = &pcp->lists[migratetype];
 617                } while (list_empty(list));
 618
 619                /* This is the only non-empty list. Free them all. */
 620                if (batch_free == MIGRATE_PCPTYPES)
 621                        batch_free = to_free;
 622
 623                do {
 624                        page = list_entry(list->prev, struct page, lru);
 625                        /* must delete as __free_one_page list manipulates */
 626                        list_del(&page->lru);
 627                        /* MIGRATE_MOVABLE list may include MIGRATE_RESERVEs */
 628                        __free_one_page(page, zone, 0, page_private(page));
 629                        trace_mm_page_pcpu_drain(page, 0, page_private(page));
 630                } while (--to_free && --batch_free && !list_empty(list));
 631        }
 632        __mod_zone_page_state(zone, NR_FREE_PAGES, count);
 633        spin_unlock(&zone->lock);
 634}
 635
 636static void free_one_page(struct zone *zone, struct page *page, int order,
 637                                int migratetype)
 638{
 639        spin_lock(&zone->lock);
 640        zone->all_unreclaimable = 0;
 641        zone->pages_scanned = 0;
 642
 643        __free_one_page(page, zone, order, migratetype);
 644        __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
 645        spin_unlock(&zone->lock);
 646}
 647
 648static bool free_pages_prepare(struct page *page, unsigned int order)
 649{
 650        int i;
 651        int bad = 0;
 652
 653        trace_mm_page_free_direct(page, order);
 654        kmemcheck_free_shadow(page, order);
 655
 656        if (PageAnon(page))
 657                page->mapping = NULL;
 658        for (i = 0; i < (1 << order); i++)
 659                bad += free_pages_check(page + i);
 660        if (bad)
 661                return false;
 662
 663        if (!PageHighMem(page)) {
 664                debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
 665                debug_check_no_obj_freed(page_address(page),
 666                                           PAGE_SIZE << order);
 667        }
 668        arch_free_page(page, order);
 669        kernel_map_pages(page, 1 << order, 0);
 670
 671        return true;
 672}
 673
 674static void __free_pages_ok(struct page *page, unsigned int order)
 675{
 676        unsigned long flags;
 677        int wasMlocked = __TestClearPageMlocked(page);
 678
 679        if (!free_pages_prepare(page, order))
 680                return;
 681
 682        local_irq_save(flags);
 683        if (unlikely(wasMlocked))
 684                free_page_mlock(page);
 685        __count_vm_events(PGFREE, 1 << order);
 686        free_one_page(page_zone(page), page, order,
 687                                        get_pageblock_migratetype(page));
 688        local_irq_restore(flags);
 689}
 690
 691/*
 692 * permit the bootmem allocator to evade page validation on high-order frees
 693 */
 694void __meminit __free_pages_bootmem(struct page *page, unsigned int order)
 695{
 696        if (order == 0) {
 697                __ClearPageReserved(page);
 698                set_page_count(page, 0);
 699                set_page_refcounted(page);
 700                __free_page(page);
 701        } else {
 702                int loop;
 703
 704                prefetchw(page);
 705                for (loop = 0; loop < BITS_PER_LONG; loop++) {
 706                        struct page *p = &page[loop];
 707
 708                        if (loop + 1 < BITS_PER_LONG)
 709                                prefetchw(p + 1);
 710                        __ClearPageReserved(p);
 711                        set_page_count(p, 0);
 712                }
 713
 714                set_page_refcounted(page);
 715                __free_pages(page, order);
 716        }
 717}
 718
 719
 720/*
 721 * The order of subdivision here is critical for the IO subsystem.
 722 * Please do not alter this order without good reasons and regression
 723 * testing. Specifically, as large blocks of memory are subdivided,
 724 * the order in which smaller blocks are delivered depends on the order
 725 * they're subdivided in this function. This is the primary factor
 726 * influencing the order in which pages are delivered to the IO
 727 * subsystem according to empirical testing, and this is also justified
 728 * by considering the behavior of a buddy system containing a single
 729 * large block of memory acted on by a series of small allocations.
 730 * This behavior is a critical factor in sglist merging's success.
 731 *
 732 * -- wli
 733 */
 734static inline void expand(struct zone *zone, struct page *page,
 735        int low, int high, struct free_area *area,
 736        int migratetype)
 737{
 738        unsigned long size = 1 << high;
 739
 740        while (high > low) {
 741                area--;
 742                high--;
 743                size >>= 1;
 744                VM_BUG_ON(bad_range(zone, &page[size]));
 745                list_add(&page[size].lru, &area->free_list[migratetype]);
 746                area->nr_free++;
 747                set_page_order(&page[size], high);
 748        }
 749}
 750
 751/*
 752 * This page is about to be returned from the page allocator
 753 */
 754static inline int check_new_page(struct page *page)
 755{
 756        if (unlikely(page_mapcount(page) |
 757                (page->mapping != NULL)  |
 758                (atomic_read(&page->_count) != 0)  |
 759                (page->flags & PAGE_FLAGS_CHECK_AT_PREP) |
 760                (mem_cgroup_bad_page_check(page)))) {
 761                bad_page(page);
 762                return 1;
 763        }
 764        return 0;
 765}
 766
 767static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
 768{
 769        int i;
 770
 771        for (i = 0; i < (1 << order); i++) {
 772                struct page *p = page + i;
 773                if (unlikely(check_new_page(p)))
 774                        return 1;
 775        }
 776
 777        set_page_private(page, 0);
 778        set_page_refcounted(page);
 779
 780        arch_alloc_page(page, order);
 781        kernel_map_pages(page, 1 << order, 1);
 782
 783        if (gfp_flags & __GFP_ZERO)
 784                prep_zero_page(page, order, gfp_flags);
 785
 786        if (order && (gfp_flags & __GFP_COMP))
 787                prep_compound_page(page, order);
 788
 789        return 0;
 790}
 791
 792/*
 793 * Go through the free lists for the given migratetype and remove
 794 * the smallest available page from the freelists
 795 */
 796static inline
 797struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
 798                                                int migratetype)
 799{
 800        unsigned int current_order;
 801        struct free_area * area;
 802        struct page *page;
 803
 804        /* Find a page of the appropriate size in the preferred list */
 805        for (current_order = order; current_order < MAX_ORDER; ++current_order) {
 806                area = &(zone->free_area[current_order]);
 807                if (list_empty(&area->free_list[migratetype]))
 808                        continue;
 809
 810                page = list_entry(area->free_list[migratetype].next,
 811                                                        struct page, lru);
 812                list_del(&page->lru);
 813                rmv_page_order(page);
 814                area->nr_free--;
 815                expand(zone, page, order, current_order, area, migratetype);
 816                return page;
 817        }
 818
 819        return NULL;
 820}
 821
 822
 823/*
 824 * This array describes the order lists are fallen back to when
 825 * the free lists for the desirable migrate type are depleted
 826 */
 827static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
 828        [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
 829        [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
 830        [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
 831        [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */
 832};
 833
 834/*
 835 * Move the free pages in a range to the free lists of the requested type.
 836 * Note that start_page and end_pages are not aligned on a pageblock
 837 * boundary. If alignment is required, use move_freepages_block()
 838 */
 839static int move_freepages(struct zone *zone,
 840                          struct page *start_page, struct page *end_page,
 841                          int migratetype)
 842{
 843        struct page *page;
 844        unsigned long order;
 845        int pages_moved = 0;
 846
 847#ifndef CONFIG_HOLES_IN_ZONE
 848        /*
 849         * page_zone is not safe to call in this context when
 850         * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
 851         * anyway as we check zone boundaries in move_freepages_block().
 852         * Remove at a later date when no bug reports exist related to
 853         * grouping pages by mobility
 854         */
 855        BUG_ON(page_zone(start_page) != page_zone(end_page));
 856#endif
 857
 858        for (page = start_page; page <= end_page;) {
 859                /* Make sure we are not inadvertently changing nodes */
 860                VM_BUG_ON(page_to_nid(page) != zone_to_nid(zone));
 861
 862                if (!pfn_valid_within(page_to_pfn(page))) {
 863                        page++;
 864                        continue;
 865                }
 866
 867                if (!PageBuddy(page)) {
 868                        page++;
 869                        continue;
 870                }
 871
 872                order = page_order(page);
 873                list_move(&page->lru,
 874                          &zone->free_area[order].free_list[migratetype]);
 875                page += 1 << order;
 876                pages_moved += 1 << order;
 877        }
 878
 879        return pages_moved;
 880}
 881
 882static int move_freepages_block(struct zone *zone, struct page *page,
 883                                int migratetype)
 884{
 885        unsigned long start_pfn, end_pfn;
 886        struct page *start_page, *end_page;
 887
 888        start_pfn = page_to_pfn(page);
 889        start_pfn = start_pfn & ~(pageblock_nr_pages-1);
 890        start_page = pfn_to_page(start_pfn);
 891        end_page = start_page + pageblock_nr_pages - 1;
 892        end_pfn = start_pfn + pageblock_nr_pages - 1;
 893
 894        /* Do not cross zone boundaries */
 895        if (start_pfn < zone->zone_start_pfn)
 896                start_page = page;
 897        if (end_pfn >= zone->zone_start_pfn + zone->spanned_pages)
 898                return 0;
 899
 900        return move_freepages(zone, start_page, end_page, migratetype);
 901}
 902
 903static void change_pageblock_range(struct page *pageblock_page,
 904                                        int start_order, int migratetype)
 905{
 906        int nr_pageblocks = 1 << (start_order - pageblock_order);
 907
 908        while (nr_pageblocks--) {
 909                set_pageblock_migratetype(pageblock_page, migratetype);
 910                pageblock_page += pageblock_nr_pages;
 911        }
 912}
 913
 914/* Remove an element from the buddy allocator from the fallback list */
 915static inline struct page *
 916__rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
 917{
 918        struct free_area * area;
 919        int current_order;
 920        struct page *page;
 921        int migratetype, i;
 922
 923        /* Find the largest possible block of pages in the other list */
 924        for (current_order = MAX_ORDER-1; current_order >= order;
 925                                                --current_order) {
 926                for (i = 0; i < MIGRATE_TYPES - 1; i++) {
 927                        migratetype = fallbacks[start_migratetype][i];
 928
 929                        /* MIGRATE_RESERVE handled later if necessary */
 930                        if (migratetype == MIGRATE_RESERVE)
 931                                continue;
 932
 933                        area = &(zone->free_area[current_order]);
 934                        if (list_empty(&area->free_list[migratetype]))
 935                                continue;
 936
 937                        page = list_entry(area->free_list[migratetype].next,
 938                                        struct page, lru);
 939                        area->nr_free--;
 940
 941                        /*
 942                         * If breaking a large block of pages, move all free
 943                         * pages to the preferred allocation list. If falling
 944                         * back for a reclaimable kernel allocation, be more
 945                         * aggressive about taking ownership of free pages
 946                         */
 947                        if (unlikely(current_order >= (pageblock_order >> 1)) ||
 948                                        start_migratetype == MIGRATE_RECLAIMABLE ||
 949                                        page_group_by_mobility_disabled) {
 950                                unsigned long pages;
 951                                pages = move_freepages_block(zone, page,
 952                                                                start_migratetype);
 953
 954                                /* Claim the whole block if over half of it is free */
 955                                if (pages >= (1 << (pageblock_order-1)) ||
 956                                                page_group_by_mobility_disabled)
 957                                        set_pageblock_migratetype(page,
 958                                                                start_migratetype);
 959
 960                                migratetype = start_migratetype;
 961                        }
 962
 963                        /* Remove the page from the freelists */
 964                        list_del(&page->lru);
 965                        rmv_page_order(page);
 966
 967                        /* Take ownership for orders >= pageblock_order */
 968                        if (current_order >= pageblock_order)
 969                                change_pageblock_range(page, current_order,
 970                                                        start_migratetype);
 971
 972                        expand(zone, page, order, current_order, area, migratetype);
 973
 974                        trace_mm_page_alloc_extfrag(page, order, current_order,
 975                                start_migratetype, migratetype);
 976
 977                        return page;
 978                }
 979        }
 980
 981        return NULL;
 982}
 983
 984/*
 985 * Do the hard work of removing an element from the buddy allocator.
 986 * Call me with the zone->lock already held.
 987 */
 988static struct page *__rmqueue(struct zone *zone, unsigned int order,
 989                                                int migratetype)
 990{
 991        struct page *page;
 992
 993retry_reserve:
 994        page = __rmqueue_smallest(zone, order, migratetype);
 995
 996        if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
 997                page = __rmqueue_fallback(zone, order, migratetype);
 998
 999                /*
1000                 * Use MIGRATE_RESERVE rather than fail an allocation. goto
1001                 * is used because __rmqueue_smallest is an inline function
1002                 * and we want just one call site
1003                 */
1004                if (!page) {
1005                        migratetype = MIGRATE_RESERVE;
1006                        goto retry_reserve;
1007                }
1008        }
1009
1010        trace_mm_page_alloc_zone_locked(page, order, migratetype);
1011        return page;
1012}
1013
1014/* 
1015 * Obtain a specified number of elements from the buddy allocator, all under
1016 * a single hold of the lock, for efficiency.  Add them to the supplied list.
1017 * Returns the number of new pages which were placed at *list.
1018 */
1019static int rmqueue_bulk(struct zone *zone, unsigned int order, 
1020                        unsigned long count, struct list_head *list,
1021                        int migratetype, int cold)
1022{
1023        int i;
1024        
1025        spin_lock(&zone->lock);
1026        for (i = 0; i < count; ++i) {
1027                struct page *page = __rmqueue(zone, order, migratetype);
1028                if (unlikely(page == NULL))
1029                        break;
1030
1031                /*
1032                 * Split buddy pages returned by expand() are received here
1033                 * in physical page order. The page is added to the callers and
1034                 * list and the list head then moves forward. From the callers
1035                 * perspective, the linked list is ordered by page number in
1036                 * some conditions. This is useful for IO devices that can
1037                 * merge IO requests if the physical pages are ordered
1038                 * properly.
1039                 */
1040                if (likely(cold == 0))
1041                        list_add(&page->lru, list);
1042                else
1043                        list_add_tail(&page->lru, list);
1044                set_page_private(page, migratetype);
1045                list = &page->lru;
1046        }
1047        __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
1048        spin_unlock(&zone->lock);
1049        return i;
1050}
1051
1052#ifdef CONFIG_NUMA
1053/*
1054 * Called from the vmstat counter updater to drain pagesets of this
1055 * currently executing processor on remote nodes after they have
1056 * expired.
1057 *
1058 * Note that this function must be called with the thread pinned to
1059 * a single processor.
1060 */
1061void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
1062{
1063        unsigned long flags;
1064        int to_drain;
1065
1066        local_irq_save(flags);
1067        if (pcp->count >= pcp->batch)
1068                to_drain = pcp->batch;
1069        else
1070                to_drain = pcp->count;
1071        free_pcppages_bulk(zone, to_drain, pcp);
1072        pcp->count -= to_drain;
1073        local_irq_restore(flags);
1074}
1075#endif
1076
1077/*
1078 * Drain pages of the indicated processor.
1079 *
1080 * The processor must either be the current processor and the
1081 * thread pinned to the current processor or a processor that
1082 * is not online.
1083 */
1084static void drain_pages(unsigned int cpu)
1085{
1086        unsigned long flags;
1087        struct zone *zone;
1088
1089        for_each_populated_zone(zone) {
1090                struct per_cpu_pageset *pset;
1091                struct per_cpu_pages *pcp;
1092
1093                local_irq_save(flags);
1094                pset = per_cpu_ptr(zone->pageset, cpu);
1095
1096                pcp = &pset->pcp;
1097                if (pcp->count) {
1098                        free_pcppages_bulk(zone, pcp->count, pcp);
1099                        pcp->count = 0;
1100                }
1101                local_irq_restore(flags);
1102        }
1103}
1104
1105/*
1106 * Spill all of this CPU's per-cpu pages back into the buddy allocator.
1107 */
1108void drain_local_pages(void *arg)
1109{
1110        drain_pages(smp_processor_id());
1111}
1112
1113/*
1114 * Spill all the per-cpu pages from all CPUs back into the buddy allocator
1115 */
1116void drain_all_pages(void)
1117{
1118        on_each_cpu(drain_local_pages, NULL, 1);
1119}
1120
1121#ifdef CONFIG_HIBERNATION
1122
1123void mark_free_pages(struct zone *zone)
1124{
1125        unsigned long pfn, max_zone_pfn;
1126        unsigned long flags;
1127        int order, t;
1128        struct list_head *curr;
1129
1130        if (!zone->spanned_pages)
1131                return;
1132
1133        spin_lock_irqsave(&zone->lock, flags);
1134
1135        max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
1136        for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
1137                if (pfn_valid(pfn)) {
1138                        struct page *page = pfn_to_page(pfn);
1139
1140                        if (!swsusp_page_is_forbidden(page))
1141                                swsusp_unset_page_free(page);
1142                }
1143
1144        for_each_migratetype_order(order, t) {
1145                list_for_each(curr, &zone->free_area[order].free_list[t]) {
1146                        unsigned long i;
1147
1148                        pfn = page_to_pfn(list_entry(curr, struct page, lru));
1149                        for (i = 0; i < (1UL << order); i++)
1150                                swsusp_set_page_free(pfn_to_page(pfn + i));
1151                }
1152        }
1153        spin_unlock_irqrestore(&zone->lock, flags);
1154}
1155#endif /* CONFIG_PM */
1156
1157/*
1158 * Free a 0-order page
1159 * cold == 1 ? free a cold page : free a hot page
1160 */
1161void free_hot_cold_page(struct page *page, int cold)
1162{
1163        struct zone *zone = page_zone(page);
1164        struct per_cpu_pages *pcp;
1165        unsigned long flags;
1166        int migratetype;
1167        int wasMlocked = __TestClearPageMlocked(page);
1168
1169        if (!free_pages_prepare(page, 0))
1170                return;
1171
1172        migratetype = get_pageblock_migratetype(page);
1173        set_page_private(page, migratetype);
1174        local_irq_save(flags);
1175        if (unlikely(wasMlocked))
1176                free_page_mlock(page);
1177        __count_vm_event(PGFREE);
1178
1179        /*
1180         * We only track unmovable, reclaimable and movable on pcp lists.
1181         * Free ISOLATE pages back to the allocator because they are being
1182         * offlined but treat RESERVE as movable pages so we can get those
1183         * areas back if necessary. Otherwise, we may have to free
1184         * excessively into the page allocator
1185         */
1186        if (migratetype >= MIGRATE_PCPTYPES) {
1187                if (unlikely(migratetype == MIGRATE_ISOLATE)) {
1188                        free_one_page(zone, page, 0, migratetype);
1189                        goto out;
1190                }
1191                migratetype = MIGRATE_MOVABLE;
1192        }
1193
1194        pcp = &this_cpu_ptr(zone->pageset)->pcp;
1195        if (cold)
1196                list_add_tail(&page->lru, &pcp->lists[migratetype]);
1197        else
1198                list_add(&page->lru, &pcp->lists[migratetype]);
1199        pcp->count++;
1200        if (pcp->count >= pcp->high) {
1201                free_pcppages_bulk(zone, pcp->batch, pcp);
1202                pcp->count -= pcp->batch;
1203        }
1204
1205out:
1206        local_irq_restore(flags);
1207}
1208
1209/*
1210 * split_page takes a non-compound higher-order page, and splits it into
1211 * n (1<<order) sub-pages: page[0..n]
1212 * Each sub-page must be freed individually.
1213 *
1214 * Note: this is probably too low level an operation for use in drivers.
1215 * Please consult with lkml before using this in your driver.
1216 */
1217void split_page(struct page *page, unsigned int order)
1218{
1219        int i;
1220
1221        VM_BUG_ON(PageCompound(page));
1222        VM_BUG_ON(!page_count(page));
1223
1224#ifdef CONFIG_KMEMCHECK
1225        /*
1226         * Split shadow pages too, because free(page[0]) would
1227         * otherwise free the whole shadow.
1228         */
1229        if (kmemcheck_page_is_tracked(page))
1230                split_page(virt_to_page(page[0].shadow), order);
1231#endif
1232
1233        for (i = 1; i < (1 << order); i++)
1234                set_page_refcounted(page + i);
1235}
1236
1237/*
1238 * Similar to split_page except the page is already free. As this is only
1239 * being used for migration, the migratetype of the block also changes.
1240 * As this is called with interrupts disabled, the caller is responsible
1241 * for calling arch_alloc_page() and kernel_map_page() after interrupts
1242 * are enabled.
1243 *
1244 * Note: this is probably too low level an operation for use in drivers.
1245 * Please consult with lkml before using this in your driver.
1246 */
1247int split_free_page(struct page *page)
1248{
1249        unsigned int order;
1250        unsigned long watermark;
1251        struct zone *zone;
1252
1253        BUG_ON(!PageBuddy(page));
1254
1255        zone = page_zone(page);
1256        order = page_order(page);
1257
1258        /* Obey watermarks as if the page was being allocated */
1259        watermark = low_wmark_pages(zone) + (1 << order);
1260        if (!zone_watermark_ok(zone, 0, watermark, 0, 0))
1261                return 0;
1262
1263        /* Remove page from free list */
1264        list_del(&page->lru);
1265        zone->free_area[order].nr_free--;
1266        rmv_page_order(page);
1267        __mod_zone_page_state(zone, NR_FREE_PAGES, -(1UL << order));
1268
1269        /* Split into individual pages */
1270        set_page_refcounted(page);
1271        split_page(page, order);
1272
1273        if (order >= pageblock_order - 1) {
1274                struct page *endpage = page + (1 << order) - 1;
1275                for (; page < endpage; page += pageblock_nr_pages)
1276                        set_pageblock_migratetype(page, MIGRATE_MOVABLE);
1277        }
1278
1279        return 1 << order;
1280}
1281
1282/*
1283 * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
1284 * we cheat by calling it from here, in the order > 0 path.  Saves a branch
1285 * or two.
1286 */
1287static inline
1288struct page *buffered_rmqueue(struct zone *preferred_zone,
1289                        struct zone *zone, int order, gfp_t gfp_flags,
1290                        int migratetype)
1291{
1292        unsigned long flags;
1293        struct page *page;
1294        int cold = !!(gfp_flags & __GFP_COLD);
1295
1296again:
1297        if (likely(order == 0)) {
1298                struct per_cpu_pages *pcp;
1299                struct list_head *list;
1300
1301                local_irq_save(flags);
1302                pcp = &this_cpu_ptr(zone->pageset)->pcp;
1303                list = &pcp->lists[migratetype];
1304                if (list_empty(list)) {
1305                        pcp->count += rmqueue_bulk(zone, 0,
1306                                        pcp->batch, list,
1307                                        migratetype, cold);
1308                        if (unlikely(list_empty(list)))
1309                                goto failed;
1310                }
1311
1312                if (cold)
1313                        page = list_entry(list->prev, struct page, lru);
1314                else
1315                        page = list_entry(list->next, struct page, lru);
1316
1317                list_del(&page->lru);
1318                pcp->count--;
1319        } else {
1320                if (unlikely(gfp_flags & __GFP_NOFAIL)) {
1321                        /*
1322                         * __GFP_NOFAIL is not to be used in new code.
1323                         *
1324                         * All __GFP_NOFAIL callers should be fixed so that they
1325                         * properly detect and handle allocation failures.
1326                         *
1327                         * We most definitely don't want callers attempting to
1328                         * allocate greater than order-1 page units with
1329                         * __GFP_NOFAIL.
1330                         */
1331                        WARN_ON_ONCE(order > 1);
1332                }
1333                spin_lock_irqsave(&zone->lock, flags);
1334                page = __rmqueue(zone, order, migratetype);
1335                spin_unlock(&zone->lock);
1336                if (!page)
1337                        goto failed;
1338                __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));
1339        }
1340
1341        __count_zone_vm_events(PGALLOC, zone, 1 << order);
1342        zone_statistics(preferred_zone, zone, gfp_flags);
1343        local_irq_restore(flags);
1344
1345        VM_BUG_ON(bad_range(zone, page));
1346        if (prep_new_page(page, order, gfp_flags))
1347                goto again;
1348        return page;
1349
1350failed:
1351        local_irq_restore(flags);
1352        return NULL;
1353}
1354
1355/* The ALLOC_WMARK bits are used as an index to zone->watermark */
1356#define ALLOC_WMARK_MIN         WMARK_MIN
1357#define ALLOC_WMARK_LOW         WMARK_LOW
1358#define ALLOC_WMARK_HIGH        WMARK_HIGH
1359#define ALLOC_NO_WATERMARKS     0x04 /* don't check watermarks at all */
1360
1361/* Mask to get the watermark bits */
1362#define ALLOC_WMARK_MASK        (ALLOC_NO_WATERMARKS-1)
1363
1364#define ALLOC_HARDER            0x10 /* try to alloc harder */
1365#define ALLOC_HIGH              0x20 /* __GFP_HIGH set */
1366#define ALLOC_CPUSET            0x40 /* check for correct cpuset */
1367
1368#ifdef CONFIG_FAIL_PAGE_ALLOC
1369
1370static struct fail_page_alloc_attr {
1371        struct fault_attr attr;
1372
1373        u32 ignore_gfp_highmem;
1374        u32 ignore_gfp_wait;
1375        u32 min_order;
1376
1377#ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
1378
1379        struct dentry *ignore_gfp_highmem_file;
1380        struct dentry *ignore_gfp_wait_file;
1381        struct dentry *min_order_file;
1382
1383#endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
1384
1385} fail_page_alloc = {
1386        .attr = FAULT_ATTR_INITIALIZER,
1387        .ignore_gfp_wait = 1,
1388        .ignore_gfp_highmem = 1,
1389        .min_order = 1,
1390};
1391
1392static int __init setup_fail_page_alloc(char *str)
1393{
1394        return setup_fault_attr(&fail_page_alloc.attr, str);
1395}
1396__setup("fail_page_alloc=", setup_fail_page_alloc);
1397
1398static int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1399{
1400        if (order < fail_page_alloc.min_order)
1401                return 0;
1402        if (gfp_mask & __GFP_NOFAIL)
1403                return 0;
1404        if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
1405                return 0;
1406        if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT))
1407                return 0;
1408
1409        return should_fail(&fail_page_alloc.attr, 1 << order);
1410}
1411
1412#ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
1413
1414static int __init fail_page_alloc_debugfs(void)
1415{
1416        mode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
1417        struct dentry *dir;
1418        int err;
1419
1420        err = init_fault_attr_dentries(&fail_page_alloc.attr,
1421                                       "fail_page_alloc");
1422        if (err)
1423                return err;
1424        dir = fail_page_alloc.attr.dentries.dir;
1425
1426        fail_page_alloc.ignore_gfp_wait_file =
1427                debugfs_create_bool("ignore-gfp-wait", mode, dir,
1428                                      &fail_page_alloc.ignore_gfp_wait);
1429
1430        fail_page_alloc.ignore_gfp_highmem_file =
1431                debugfs_create_bool("ignore-gfp-highmem", mode, dir,
1432                                      &fail_page_alloc.ignore_gfp_highmem);
1433        fail_page_alloc.min_order_file =
1434                debugfs_create_u32("min-order", mode, dir,
1435                                   &fail_page_alloc.min_order);
1436
1437        if (!fail_page_alloc.ignore_gfp_wait_file ||
1438            !fail_page_alloc.ignore_gfp_highmem_file ||
1439            !fail_page_alloc.min_order_file) {
1440                err = -ENOMEM;
1441                debugfs_remove(fail_page_alloc.ignore_gfp_wait_file);
1442                debugfs_remove(fail_page_alloc.ignore_gfp_highmem_file);
1443                debugfs_remove(fail_page_alloc.min_order_file);
1444                cleanup_fault_attr_dentries(&fail_page_alloc.attr);
1445        }
1446
1447        return err;
1448}
1449
1450late_initcall(fail_page_alloc_debugfs);
1451
1452#endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
1453
1454#else /* CONFIG_FAIL_PAGE_ALLOC */
1455
1456static inline int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1457{
1458        return 0;
1459}
1460
1461#endif /* CONFIG_FAIL_PAGE_ALLOC */
1462
1463/*
1464 * Return true if free pages are above 'mark'. This takes into account the order
1465 * of the allocation.
1466 */
1467static bool __zone_watermark_ok(struct zone *z, int order, unsigned long mark,
1468                      int classzone_idx, int alloc_flags, long free_pages)
1469{
1470        /* free_pages my go negative - that's OK */
1471        long min = mark;
1472        int o;
1473
1474        free_pages -= (1 << order) + 1;
1475        if (alloc_flags & ALLOC_HIGH)
1476                min -= min / 2;
1477        if (alloc_flags & ALLOC_HARDER)
1478                min -= min / 4;
1479
1480        if (free_pages <= min + z->lowmem_reserve[classzone_idx])
1481                return false;
1482        for (o = 0; o < order; o++) {
1483                /* At the next order, this order's pages become unavailable */
1484                free_pages -= z->free_area[o].nr_free << o;
1485
1486                /* Require fewer higher order pages to be free */
1487                min >>= 1;
1488
1489                if (free_pages <= min)
1490                        return false;
1491        }
1492        return true;
1493}
1494
1495bool zone_watermark_ok(struct zone *z, int order, unsigned long mark,
1496                      int classzone_idx, int alloc_flags)
1497{
1498        return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
1499                                        zone_page_state(z, NR_FREE_PAGES));
1500}
1501
1502bool zone_watermark_ok_safe(struct zone *z, int order, unsigned long mark,
1503                      int classzone_idx, int alloc_flags)
1504{
1505        long free_pages = zone_page_state(z, NR_FREE_PAGES);
1506
1507        if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
1508                free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);
1509
1510        return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
1511                                                                free_pages);
1512}
1513
1514#ifdef CONFIG_NUMA
1515/*
1516 * zlc_setup - Setup for "zonelist cache".  Uses cached zone data to
1517 * skip over zones that are not allowed by the cpuset, or that have
1518 * been recently (in last second) found to be nearly full.  See further
1519 * comments in mmzone.h.  Reduces cache footprint of zonelist scans
1520 * that have to skip over a lot of full or unallowed zones.
1521 *
1522 * If the zonelist cache is present in the passed in zonelist, then
1523 * returns a pointer to the allowed node mask (either the current
1524 * tasks mems_allowed, or node_states[N_HIGH_MEMORY].)
1525 *
1526 * If the zonelist cache is not available for this zonelist, does
1527 * nothing and returns NULL.
1528 *
1529 * If the fullzones BITMAP in the zonelist cache is stale (more than
1530 * a second since last zap'd) then we zap it out (clear its bits.)
1531 *
1532 * We hold off even calling zlc_setup, until after we've checked the
1533 * first zone in the zonelist, on the theory that most allocations will
1534 * be satisfied from that first zone, so best to examine that zone as
1535 * quickly as we can.
1536 */
1537static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1538{
1539        struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1540        nodemask_t *allowednodes;       /* zonelist_cache approximation */
1541
1542        zlc = zonelist->zlcache_ptr;
1543        if (!zlc)
1544                return NULL;
1545
1546        if (time_after(jiffies, zlc->last_full_zap + HZ)) {
1547                bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1548                zlc->last_full_zap = jiffies;
1549        }
1550
1551        allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ?
1552                                        &cpuset_current_mems_allowed :
1553                                        &node_states[N_HIGH_MEMORY];
1554        return allowednodes;
1555}
1556
1557/*
1558 * Given 'z' scanning a zonelist, run a couple of quick checks to see
1559 * if it is worth looking at further for free memory:
1560 *  1) Check that the zone isn't thought to be full (doesn't have its
1561 *     bit set in the zonelist_cache fullzones BITMAP).
1562 *  2) Check that the zones node (obtained from the zonelist_cache
1563 *     z_to_n[] mapping) is allowed in the passed in allowednodes mask.
1564 * Return true (non-zero) if zone is worth looking at further, or
1565 * else return false (zero) if it is not.
1566 *
1567 * This check -ignores- the distinction between various watermarks,
1568 * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ...  If a zone is
1569 * found to be full for any variation of these watermarks, it will
1570 * be considered full for up to one second by all requests, unless
1571 * we are so low on memory on all allowed nodes that we are forced
1572 * into the second scan of the zonelist.
1573 *
1574 * In the second scan we ignore this zonelist cache and exactly
1575 * apply the watermarks to all zones, even it is slower to do so.
1576 * We are low on memory in the second scan, and should leave no stone
1577 * unturned looking for a free page.
1578 */
1579static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1580                                                nodemask_t *allowednodes)
1581{
1582        struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1583        int i;                          /* index of *z in zonelist zones */
1584        int n;                          /* node that zone *z is on */
1585
1586        zlc = zonelist->zlcache_ptr;
1587        if (!zlc)
1588                return 1;
1589
1590        i = z - zonelist->_zonerefs;
1591        n = zlc->z_to_n[i];
1592
1593        /* This zone is worth trying if it is allowed but not full */
1594        return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones);
1595}
1596
1597/*
1598 * Given 'z' scanning a zonelist, set the corresponding bit in
1599 * zlc->fullzones, so that subsequent attempts to allocate a page
1600 * from that zone don't waste time re-examining it.
1601 */
1602static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1603{
1604        struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1605        int i;                          /* index of *z in zonelist zones */
1606
1607        zlc = zonelist->zlcache_ptr;
1608        if (!zlc)
1609                return;
1610
1611        i = z - zonelist->_zonerefs;
1612
1613        set_bit(i, zlc->fullzones);
1614}
1615
1616#else   /* CONFIG_NUMA */
1617
1618static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1619{
1620        return NULL;
1621}
1622
1623static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1624                                nodemask_t *allowednodes)
1625{
1626        return 1;
1627}
1628
1629static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1630{
1631}
1632#endif  /* CONFIG_NUMA */
1633
1634/*
1635 * get_page_from_freelist goes through the zonelist trying to allocate
1636 * a page.
1637 */
1638static struct page *
1639get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
1640                struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
1641                struct zone *preferred_zone, int migratetype)
1642{
1643        struct zoneref *z;
1644        struct page *page = NULL;
1645        int classzone_idx;
1646        struct zone *zone;
1647        nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
1648        int zlc_active = 0;             /* set if using zonelist_cache */
1649        int did_zlc_setup = 0;          /* just call zlc_setup() one time */
1650
1651        classzone_idx = zone_idx(preferred_zone);
1652zonelist_scan:
1653        /*
1654         * Scan zonelist, looking for a zone with enough free.
1655         * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1656         */
1657        for_each_zone_zonelist_nodemask(zone, z, zonelist,
1658                                                high_zoneidx, nodemask) {
1659                if (NUMA_BUILD && zlc_active &&
1660                        !zlc_zone_worth_trying(zonelist, z, allowednodes))
1661                                continue;
1662                if ((alloc_flags & ALLOC_CPUSET) &&
1663                        !cpuset_zone_allowed_softwall(zone, gfp_mask))
1664                                goto try_next_zone;
1665
1666                BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
1667                if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
1668                        unsigned long mark;
1669                        int ret;
1670
1671                        mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
1672                        if (zone_watermark_ok(zone, order, mark,
1673                                    classzone_idx, alloc_flags))
1674                                goto try_this_zone;
1675
1676                        if (zone_reclaim_mode == 0)
1677                                goto this_zone_full;
1678
1679                        ret = zone_reclaim(zone, gfp_mask, order);
1680                        switch (ret) {
1681                        case ZONE_RECLAIM_NOSCAN:
1682                                /* did not scan */
1683                                goto try_next_zone;
1684                        case ZONE_RECLAIM_FULL:
1685                                /* scanned but unreclaimable */
1686                                goto this_zone_full;
1687                        default:
1688                                /* did we reclaim enough */
1689                                if (!zone_watermark_ok(zone, order, mark,
1690                                                classzone_idx, alloc_flags))
1691                                        goto this_zone_full;
1692                        }
1693                }
1694
1695try_this_zone:
1696                page = buffered_rmqueue(preferred_zone, zone, order,
1697                                                gfp_mask, migratetype);
1698                if (page)
1699                        break;
1700this_zone_full:
1701                if (NUMA_BUILD)
1702                        zlc_mark_zone_full(zonelist, z);
1703try_next_zone:
1704                if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {
1705                        /*
1706                         * we do zlc_setup after the first zone is tried but only
1707                         * if there are multiple nodes make it worthwhile
1708                         */
1709                        allowednodes = zlc_setup(zonelist, alloc_flags);
1710                        zlc_active = 1;
1711                        did_zlc_setup = 1;
1712                }
1713        }
1714
1715        if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
1716                /* Disable zlc cache for second zonelist scan */
1717                zlc_active = 0;
1718                goto zonelist_scan;
1719        }
1720        return page;
1721}
1722
1723/*
1724 * Large machines with many possible nodes should not always dump per-node
1725 * meminfo in irq context.
1726 */
1727static inline bool should_suppress_show_mem(void)
1728{
1729        bool ret = false;
1730
1731#if NODES_SHIFT > 8
1732        ret = in_interrupt();
1733#endif
1734        return ret;
1735}
1736
1737static inline int
1738should_alloc_retry(gfp_t gfp_mask, unsigned int order,
1739                                unsigned long pages_reclaimed)
1740{
1741        /* Do not loop if specifically requested */
1742        if (gfp_mask & __GFP_NORETRY)
1743                return 0;
1744
1745        /*
1746         * In this implementation, order <= PAGE_ALLOC_COSTLY_ORDER
1747         * means __GFP_NOFAIL, but that may not be true in other
1748         * implementations.
1749         */
1750        if (order <= PAGE_ALLOC_COSTLY_ORDER)
1751                return 1;
1752
1753        /*
1754         * For order > PAGE_ALLOC_COSTLY_ORDER, if __GFP_REPEAT is
1755         * specified, then we retry until we no longer reclaim any pages
1756         * (above), or we've reclaimed an order of pages at least as
1757         * large as the allocation's order. In both cases, if the
1758         * allocation still fails, we stop retrying.
1759         */
1760        if (gfp_mask & __GFP_REPEAT && pages_reclaimed < (1 << order))
1761                return 1;
1762
1763        /*
1764         * Don't let big-order allocations loop unless the caller
1765         * explicitly requests that.
1766         */
1767        if (gfp_mask & __GFP_NOFAIL)
1768                return 1;
1769
1770        return 0;
1771}
1772
1773static inline struct page *
1774__alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
1775        struct zonelist *zonelist, enum zone_type high_zoneidx,
1776        nodemask_t *nodemask, struct zone *preferred_zone,
1777        int migratetype)
1778{
1779        struct page *page;
1780
1781        /* Acquire the OOM killer lock for the zones in zonelist */
1782        if (!try_set_zonelist_oom(zonelist, gfp_mask)) {
1783                schedule_timeout_uninterruptible(1);
1784                return NULL;
1785        }
1786
1787        /*
1788         * Go through the zonelist yet one more time, keep very high watermark
1789         * here, this is only to catch a parallel oom killing, we must fail if
1790         * we're still under heavy pressure.
1791         */
1792        page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask,
1793                order, zonelist, high_zoneidx,
1794                ALLOC_WMARK_HIGH|ALLOC_CPUSET,
1795                preferred_zone, migratetype);
1796        if (page)
1797                goto out;
1798
1799        if (!(gfp_mask & __GFP_NOFAIL)) {
1800                /* The OOM killer will not help higher order allocs */
1801                if (order > PAGE_ALLOC_COSTLY_ORDER)
1802                        goto out;
1803                /* The OOM killer does not needlessly kill tasks for lowmem */
1804                if (high_zoneidx < ZONE_NORMAL)
1805                        goto out;
1806                /*
1807                 * GFP_THISNODE contains __GFP_NORETRY and we never hit this.
1808                 * Sanity check for bare calls of __GFP_THISNODE, not real OOM.
1809                 * The caller should handle page allocation failure by itself if
1810                 * it specifies __GFP_THISNODE.
1811                 * Note: Hugepage uses it but will hit PAGE_ALLOC_COSTLY_ORDER.
1812                 */
1813                if (gfp_mask & __GFP_THISNODE)
1814                        goto out;
1815        }
1816        /* Exhausted what can be done so it's blamo time */
1817        out_of_memory(zonelist, gfp_mask, order, nodemask);
1818
1819out:
1820        clear_zonelist_oom(zonelist, gfp_mask);
1821        return page;
1822}
1823
1824#ifdef CONFIG_COMPACTION
1825/* Try memory compaction for high-order allocations before reclaim */
1826static struct page *
1827__alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
1828        struct zonelist *zonelist, enum zone_type high_zoneidx,
1829        nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
1830        int migratetype, unsigned long *did_some_progress,
1831        bool sync_migration)
1832{
1833        struct page *page;
1834
1835        if (!order || compaction_deferred(preferred_zone))
1836                return NULL;
1837
1838        current->flags |= PF_MEMALLOC;
1839        *did_some_progress = try_to_compact_pages(zonelist, order, gfp_mask,
1840                                                nodemask, sync_migration);
1841        current->flags &= ~PF_MEMALLOC;
1842        if (*did_some_progress != COMPACT_SKIPPED) {
1843
1844                /* Page migration frees to the PCP lists but we want merging */
1845                drain_pages(get_cpu());
1846                put_cpu();
1847
1848                page = get_page_from_freelist(gfp_mask, nodemask,
1849                                order, zonelist, high_zoneidx,
1850                                alloc_flags, preferred_zone,
1851                                migratetype);
1852                if (page) {
1853                        preferred_zone->compact_considered = 0;
1854                        preferred_zone->compact_defer_shift = 0;
1855                        count_vm_event(COMPACTSUCCESS);
1856                        return page;
1857                }
1858
1859                /*
1860                 * It's bad if compaction run occurs and fails.
1861                 * The most likely reason is that pages exist,
1862                 * but not enough to satisfy watermarks.
1863                 */
1864                count_vm_event(COMPACTFAIL);
1865                defer_compaction(preferred_zone);
1866
1867                cond_resched();
1868        }
1869
1870        return NULL;
1871}
1872#else
1873static inline struct page *
1874__alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
1875        struct zonelist *zonelist, enum zone_type high_zoneidx,
1876        nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
1877        int migratetype, unsigned long *did_some_progress,
1878        bool sync_migration)
1879{
1880        return NULL;
1881}
1882#endif /* CONFIG_COMPACTION */
1883
1884/* The really slow allocator path where we enter direct reclaim */
1885static inline struct page *
1886__alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,
1887        struct zonelist *zonelist, enum zone_type high_zoneidx,
1888        nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
1889        int migratetype, unsigned long *did_some_progress)
1890{
1891        struct page *page = NULL;
1892        struct reclaim_state reclaim_state;
1893        bool drained = false;
1894
1895        cond_resched();
1896
1897        /* We now go into synchronous reclaim */
1898        cpuset_memory_pressure_bump();
1899        current->flags |= PF_MEMALLOC;
1900        lockdep_set_current_reclaim_state(gfp_mask);
1901        reclaim_state.reclaimed_slab = 0;
1902        current->reclaim_state = &reclaim_state;
1903
1904        *did_some_progress = try_to_free_pages(zonelist, order, gfp_mask, nodemask);
1905
1906        current->reclaim_state = NULL;
1907        lockdep_clear_current_reclaim_state();
1908        current->flags &= ~PF_MEMALLOC;
1909
1910        cond_resched();
1911
1912        if (unlikely(!(*did_some_progress)))
1913                return NULL;
1914
1915retry:
1916        page = get_page_from_freelist(gfp_mask, nodemask, order,
1917                                        zonelist, high_zoneidx,
1918                                        alloc_flags, preferred_zone,
1919                                        migratetype);
1920
1921        /*
1922         * If an allocation failed after direct reclaim, it could be because
1923         * pages are pinned on the per-cpu lists. Drain them and try again
1924         */
1925        if (!page && !drained) {
1926                drain_all_pages();
1927                drained = true;
1928                goto retry;
1929        }
1930
1931        return page;
1932}
1933
1934/*
1935 * This is called in the allocator slow-path if the allocation request is of
1936 * sufficient urgency to ignore watermarks and take other desperate measures
1937 */
1938static inline struct page *
1939__alloc_pages_high_priority(gfp_t gfp_mask, unsigned int order,
1940        struct zonelist *zonelist, enum zone_type high_zoneidx,
1941        nodemask_t *nodemask, struct zone *preferred_zone,
1942        int migratetype)
1943{
1944        struct page *page;
1945
1946        do {
1947                page = get_page_from_freelist(gfp_mask, nodemask, order,
1948                        zonelist, high_zoneidx, ALLOC_NO_WATERMARKS,
1949                        preferred_zone, migratetype);
1950
1951                if (!page && gfp_mask & __GFP_NOFAIL)
1952                        wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);
1953        } while (!page && (gfp_mask & __GFP_NOFAIL));
1954
1955        return page;
1956}
1957
1958static inline
1959void wake_all_kswapd(unsigned int order, struct zonelist *zonelist,
1960                                                enum zone_type high_zoneidx,
1961                                                enum zone_type classzone_idx)
1962{
1963        struct zoneref *z;
1964        struct zone *zone;
1965
1966        for_each_zone_zonelist(zone, z, zonelist, high_zoneidx)
1967                wakeup_kswapd(zone, order, classzone_idx);
1968}
1969
1970static inline int
1971gfp_to_alloc_flags(gfp_t gfp_mask)
1972{
1973        int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
1974        const gfp_t wait = gfp_mask & __GFP_WAIT;
1975
1976        /* __GFP_HIGH is assumed to be the same as ALLOC_HIGH to save a branch. */
1977        BUILD_BUG_ON(__GFP_HIGH != (__force gfp_t) ALLOC_HIGH);
1978
1979        /*
1980         * The caller may dip into page reserves a bit more if the caller
1981         * cannot run direct reclaim, or if the caller has realtime scheduling
1982         * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
1983         * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
1984         */
1985        alloc_flags |= (__force int) (gfp_mask & __GFP_HIGH);
1986
1987        if (!wait) {
1988                /*
1989                 * Not worth trying to allocate harder for
1990                 * __GFP_NOMEMALLOC even if it can't schedule.
1991                 */
1992                if  (!(gfp_mask & __GFP_NOMEMALLOC))
1993                        alloc_flags |= ALLOC_HARDER;
1994                /*
1995                 * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
1996                 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1997                 */
1998                alloc_flags &= ~ALLOC_CPUSET;
1999        } else if (unlikely(rt_task(current)) && !in_interrupt())
2000                alloc_flags |= ALLOC_HARDER;
2001
2002        if (likely(!(gfp_mask & __GFP_NOMEMALLOC))) {
2003                if (!in_interrupt() &&
2004                    ((current->flags & PF_MEMALLOC) ||
2005                     unlikely(test_thread_flag(TIF_MEMDIE))))
2006                        alloc_flags |= ALLOC_NO_WATERMARKS;
2007        }
2008
2009        return alloc_flags;
2010}
2011
2012static inline struct page *
2013__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
2014        struct zonelist *zonelist, enum zone_type high_zoneidx,
2015        nodemask_t *nodemask, struct zone *preferred_zone,
2016        int migratetype)
2017{
2018        const gfp_t wait = gfp_mask & __GFP_WAIT;
2019        struct page *page = NULL;
2020        int alloc_flags;
2021        unsigned long pages_reclaimed = 0;
2022        unsigned long did_some_progress;
2023        bool sync_migration = false;
2024
2025        /*
2026         * In the slowpath, we sanity check order to avoid ever trying to
2027         * reclaim >= MAX_ORDER areas which will never succeed. Callers may
2028         * be using allocators in order of preference for an area that is
2029         * too large.
2030         */
2031        if (order >= MAX_ORDER) {
2032                WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
2033                return NULL;
2034        }
2035
2036        /*
2037         * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
2038         * __GFP_NOWARN set) should not cause reclaim since the subsystem
2039         * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
2040         * using a larger set of nodes after it has established that the
2041         * allowed per node queues are empty and that nodes are
2042         * over allocated.
2043         */
2044        if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
2045                goto nopage;
2046
2047restart:
2048        if (!(gfp_mask & __GFP_NO_KSWAPD))
2049                wake_all_kswapd(order, zonelist, high_zoneidx,
2050                                                zone_idx(preferred_zone));
2051
2052        /*
2053         * OK, we're below the kswapd watermark and have kicked background
2054         * reclaim. Now things get more complex, so set up alloc_flags according
2055         * to how we want to proceed.
2056         */
2057        alloc_flags = gfp_to_alloc_flags(gfp_mask);
2058
2059        /*
2060         * Find the true preferred zone if the allocation is unconstrained by
2061         * cpusets.
2062         */
2063        if (!(alloc_flags & ALLOC_CPUSET) && !nodemask)
2064                first_zones_zonelist(zonelist, high_zoneidx, NULL,
2065                                        &preferred_zone);
2066
2067rebalance:
2068        /* This is the last chance, in general, before the goto nopage. */
2069        page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
2070                        high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
2071                        preferred_zone, migratetype);
2072        if (page)
2073                goto got_pg;
2074
2075        /* Allocate without watermarks if the context allows */
2076        if (alloc_flags & ALLOC_NO_WATERMARKS) {
2077                page = __alloc_pages_high_priority(gfp_mask, order,
2078                                zonelist, high_zoneidx, nodemask,
2079                                preferred_zone, migratetype);
2080                if (page)
2081                        goto got_pg;
2082        }
2083
2084        /* Atomic allocations - we can't balance anything */
2085        if (!wait)
2086                goto nopage;
2087
2088        /* Avoid recursion of direct reclaim */
2089        if (current->flags & PF_MEMALLOC)
2090                goto nopage;
2091
2092        /* Avoid allocations with no watermarks from looping endlessly */
2093        if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
2094                goto nopage;
2095
2096        /*
2097         * Try direct compaction. The first pass is asynchronous. Subsequent
2098         * attempts after direct reclaim are synchronous
2099         */
2100        page = __alloc_pages_direct_compact(gfp_mask, order,
2101                                        zonelist, high_zoneidx,
2102                                        nodemask,
2103                                        alloc_flags, preferred_zone,
2104                                        migratetype, &did_some_progress,
2105                                        sync_migration);
2106        if (page)
2107                goto got_pg;
2108        sync_migration = !(gfp_mask & __GFP_NO_KSWAPD);
2109
2110        /* Try direct reclaim and then allocating */
2111        page = __alloc_pages_direct_reclaim(gfp_mask, order,
2112                                        zonelist, high_zoneidx,
2113                                        nodemask,
2114                                        alloc_flags, preferred_zone,
2115                                        migratetype, &did_some_progress);
2116        if (page)
2117                goto got_pg;
2118
2119        /*
2120         * If we failed to make any progress reclaiming, then we are
2121         * running out of options and have to consider going OOM
2122         */
2123        if (!did_some_progress) {
2124                if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
2125                        if (oom_killer_disabled)
2126                                goto nopage;
2127                        page = __alloc_pages_may_oom(gfp_mask, order,
2128                                        zonelist, high_zoneidx,
2129                                        nodemask, preferred_zone,
2130                                        migratetype);
2131                        if (page)
2132                                goto got_pg;
2133
2134                        if (!(gfp_mask & __GFP_NOFAIL)) {
2135                                /*
2136                                 * The oom killer is not called for high-order
2137                                 * allocations that may fail, so if no progress
2138                                 * is being made, there are no other options and
2139                                 * retrying is unlikely to help.
2140                                 */
2141                                if (order > PAGE_ALLOC_COSTLY_ORDER)
2142                                        goto nopage;
2143                                /*
2144                                 * The oom killer is not called for lowmem
2145                                 * allocations to prevent needlessly killing
2146                                 * innocent tasks.
2147                                 */
2148                                if (high_zoneidx < ZONE_NORMAL)
2149                                        goto nopage;
2150                        }
2151
2152                        goto restart;
2153                }
2154        }
2155
2156        /* Check if we should retry the allocation */
2157        pages_reclaimed += did_some_progress;
2158        if (should_alloc_retry(gfp_mask, order, pages_reclaimed)) {
2159                /* Wait for some write requests to complete then retry */
2160                wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);
2161                goto rebalance;
2162        } else {
2163                /*
2164                 * High-order allocations do not necessarily loop after
2165                 * direct reclaim and reclaim/compaction depends on compaction
2166                 * being called after reclaim so call directly if necessary
2167                 */
2168                page = __alloc_pages_direct_compact(gfp_mask, order,
2169                                        zonelist, high_zoneidx,
2170                                        nodemask,
2171                                        alloc_flags, preferred_zone,
2172                                        migratetype, &did_some_progress,
2173                                        sync_migration);
2174                if (page)
2175                        goto got_pg;
2176        }
2177
2178nopage:
2179        if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
2180                unsigned int filter = SHOW_MEM_FILTER_NODES;
2181
2182                /*
2183                 * This documents exceptions given to allocations in certain
2184                 * contexts that are allowed to allocate outside current's set
2185                 * of allowed nodes.
2186                 */
2187                if (!(gfp_mask & __GFP_NOMEMALLOC))
2188                        if (test_thread_flag(TIF_MEMDIE) ||
2189                            (current->flags & (PF_MEMALLOC | PF_EXITING)))
2190                                filter &= ~SHOW_MEM_FILTER_NODES;
2191                if (in_interrupt() || !wait)
2192                        filter &= ~SHOW_MEM_FILTER_NODES;
2193
2194                pr_warning("%s: page allocation failure. order:%d, mode:0x%x\n",
2195                        current->comm, order, gfp_mask);
2196                dump_stack();
2197                if (!should_suppress_show_mem())
2198                        show_mem(filter);
2199        }
2200        return page;
2201got_pg:
2202        if (kmemcheck_enabled)
2203                kmemcheck_pagealloc_alloc(page, order, gfp_mask);
2204        return page;
2205
2206}
2207
2208/*
2209 * This is the 'heart' of the zoned buddy allocator.
2210 */
2211struct page *
2212__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
2213                        struct zonelist *zonelist, nodemask_t *nodemask)
2214{
2215        enum zone_type high_zoneidx = gfp_zone(gfp_mask);
2216        struct zone *preferred_zone;
2217        struct page *page;
2218        int migratetype = allocflags_to_migratetype(gfp_mask);
2219
2220        gfp_mask &= gfp_allowed_mask;
2221
2222        lockdep_trace_alloc(gfp_mask);
2223
2224        might_sleep_if(gfp_mask & __GFP_WAIT);
2225
2226        if (should_fail_alloc_page(gfp_mask, order))
2227                return NULL;
2228
2229        /*
2230         * Check the zones suitable for the gfp_mask contain at least one
2231         * valid zone. It's possible to have an empty zonelist as a result
2232         * of GFP_THISNODE and a memoryless node
2233         */
2234        if (unlikely(!zonelist->_zonerefs->zone))
2235                return NULL;
2236
2237        get_mems_allowed();
2238        /* The preferred zone is used for statistics later */
2239        first_zones_zonelist(zonelist, high_zoneidx,
2240                                nodemask ? : &cpuset_current_mems_allowed,
2241                                &preferred_zone);
2242        if (!preferred_zone) {
2243                put_mems_allowed();
2244                return NULL;
2245        }
2246
2247        /* First allocation attempt */
2248        page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
2249                        zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET,
2250                        preferred_zone, migratetype);
2251        if (unlikely(!page))
2252                page = __alloc_pages_slowpath(gfp_mask, order,
2253                                zonelist, high_zoneidx, nodemask,
2254                                preferred_zone, migratetype);
2255        put_mems_allowed();
2256
2257        trace_mm_page_alloc(page, order, gfp_mask, migratetype);
2258        return page;
2259}
2260EXPORT_SYMBOL(__alloc_pages_nodemask);
2261
2262/*
2263 * Common helper functions.
2264 */
2265unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
2266{
2267        struct page *page;
2268
2269        /*
2270         * __get_free_pages() returns a 32-bit address, which cannot represent
2271         * a highmem page
2272         */
2273        VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
2274
2275        page = alloc_pages(gfp_mask, order);
2276        if (!page)
2277                return 0;
2278        return (unsigned long) page_address(page);
2279}
2280EXPORT_SYMBOL(__get_free_pages);
2281
2282unsigned long get_zeroed_page(gfp_t gfp_mask)
2283{
2284        return __get_free_pages(gfp_mask | __GFP_ZERO, 0);
2285}
2286EXPORT_SYMBOL(get_zeroed_page);
2287
2288void __pagevec_free(struct pagevec *pvec)
2289{
2290        int i = pagevec_count(pvec);
2291
2292        while (--i >= 0) {
2293                trace_mm_pagevec_free(pvec->pages[i], pvec->cold);
2294                free_hot_cold_page(pvec->pages[i], pvec->cold);
2295        }
2296}
2297
2298void __free_pages(struct page *page, unsigned int order)
2299{
2300        if (put_page_testzero(page)) {
2301                if (order == 0)
2302                        free_hot_cold_page(page, 0);
2303                else
2304                        __free_pages_ok(page, order);
2305        }
2306}
2307
2308EXPORT_SYMBOL(__free_pages);
2309
2310void free_pages(unsigned long addr, unsigned int order)
2311{
2312        if (addr != 0) {
2313                VM_BUG_ON(!virt_addr_valid((void *)addr));
2314                __free_pages(virt_to_page((void *)addr), order);
2315        }
2316}
2317
2318EXPORT_SYMBOL(free_pages);
2319
2320static void *make_alloc_exact(unsigned long addr, unsigned order, size_t size)
2321{
2322        if (addr) {
2323                unsigned long alloc_end = addr + (PAGE_SIZE << order);
2324                unsigned long used = addr + PAGE_ALIGN(size);
2325
2326                split_page(virt_to_page((void *)addr), order);
2327                while (used < alloc_end) {
2328                        free_page(used);
2329                        used += PAGE_SIZE;
2330                }
2331        }
2332        return (void *)addr;
2333}
2334
2335/**
2336 * alloc_pages_exact - allocate an exact number physically-contiguous pages.
2337 * @size: the number of bytes to allocate
2338 * @gfp_mask: GFP flags for the allocation
2339 *
2340 * This function is similar to alloc_pages(), except that it allocates the
2341 * minimum number of pages to satisfy the request.  alloc_pages() can only
2342 * allocate memory in power-of-two pages.
2343 *
2344 * This function is also limited by MAX_ORDER.
2345 *
2346 * Memory allocated by this function must be released by free_pages_exact().
2347 */
2348void *alloc_pages_exact(size_t size, gfp_t gfp_mask)
2349{
2350        unsigned int order = get_order(size);
2351        unsigned long addr;
2352
2353        addr = __get_free_pages(gfp_mask, order);
2354        return make_alloc_exact(addr, order, size);
2355}
2356EXPORT_SYMBOL(alloc_pages_exact);
2357
2358/**
2359 * alloc_pages_exact_nid - allocate an exact number of physically-contiguous
2360 *                         pages on a node.
2361 * @nid: the preferred node ID where memory should be allocated
2362 * @size: the number of bytes to allocate
2363 * @gfp_mask: GFP flags for the allocation
2364 *
2365 * Like alloc_pages_exact(), but try to allocate on node nid first before falling
2366 * back.
2367 * Note this is not alloc_pages_exact_node() which allocates on a specific node,
2368 * but is not exact.
2369 */
2370void *alloc_pages_exact_nid(int nid, size_t size, gfp_t gfp_mask)
2371{
2372        unsigned order = get_order(size);
2373        struct page *p = alloc_pages_node(nid, gfp_mask, order);
2374        if (!p)
2375                return NULL;
2376        return make_alloc_exact((unsigned long)page_address(p), order, size);
2377}
2378EXPORT_SYMBOL(alloc_pages_exact_nid);
2379
2380/**
2381 * free_pages_exact - release memory allocated via alloc_pages_exact()
2382 * @virt: the value returned by alloc_pages_exact.
2383 * @size: size of allocation, same value as passed to alloc_pages_exact().
2384 *
2385 * Release the memory allocated by a previous call to alloc_pages_exact.
2386 */
2387void free_pages_exact(void *virt, size_t size)
2388{
2389        unsigned long addr = (unsigned long)virt;
2390        unsigned long end = addr + PAGE_ALIGN(size);
2391
2392        while (addr < end) {
2393                free_page(addr);
2394                addr += PAGE_SIZE;
2395        }
2396}
2397EXPORT_SYMBOL(free_pages_exact);
2398
2399static unsigned int nr_free_zone_pages(int offset)
2400{
2401        struct zoneref *z;
2402        struct zone *zone;
2403
2404        /* Just pick one node, since fallback list is circular */
2405        unsigned int sum = 0;
2406
2407        struct zonelist *zonelist = node_zonelist(numa_node_id(), GFP_KERNEL);
2408
2409        for_each_zone_zonelist(zone, z, zonelist, offset) {
2410                unsigned long size = zone->present_pages;
2411                unsigned long high = high_wmark_pages(zone);
2412                if (size > high)
2413                        sum += size - high;
2414        }
2415
2416        return sum;
2417}
2418
2419/*
2420 * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
2421 */
2422unsigned int nr_free_buffer_pages(void)
2423{
2424        return nr_free_zone_pages(gfp_zone(GFP_USER));
2425}
2426EXPORT_SYMBOL_GPL(nr_free_buffer_pages);
2427
2428/*
2429 * Amount of free RAM allocatable within all zones
2430 */
2431unsigned int nr_free_pagecache_pages(void)
2432{
2433        return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
2434}
2435
2436static inline void show_node(struct zone *zone)
2437{
2438        if (NUMA_BUILD)
2439                printk("Node %d ", zone_to_nid(zone));
2440}
2441
2442void si_meminfo(struct sysinfo *val)
2443{
2444        val->totalram = totalram_pages;
2445        val->sharedram = 0;
2446        val->freeram = global_page_state(NR_FREE_PAGES);
2447        val->bufferram = nr_blockdev_pages();
2448        val->totalhigh = totalhigh_pages;
2449        val->freehigh = nr_free_highpages();
2450        val->mem_unit = PAGE_SIZE;
2451}
2452
2453EXPORT_SYMBOL(si_meminfo);
2454
2455#ifdef CONFIG_NUMA
2456void si_meminfo_node(struct sysinfo *val, int nid)
2457{
2458        pg_data_t *pgdat = NODE_DATA(nid);
2459
2460        val->totalram = pgdat->node_present_pages;
2461        val->freeram = node_page_state(nid, NR_FREE_PAGES);
2462#ifdef CONFIG_HIGHMEM
2463        val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
2464        val->freehigh = zone_page_state(&pgdat->node_zones[ZONE_HIGHMEM],
2465                        NR_FREE_PAGES);
2466#else
2467        val->totalhigh = 0;
2468        val->freehigh = 0;
2469#endif
2470        val->mem_unit = PAGE_SIZE;
2471}
2472#endif
2473
2474/*
2475 * Determine whether the zone's node should be displayed or not, depending on
2476 * whether SHOW_MEM_FILTER_NODES was passed to __show_free_areas().
2477 */
2478static bool skip_free_areas_zone(unsigned int flags, const struct zone *zone)
2479{
2480        bool ret = false;
2481
2482        if (!(flags & SHOW_MEM_FILTER_NODES))
2483                goto out;
2484
2485        get_mems_allowed();
2486        ret = !node_isset(zone->zone_pgdat->node_id,
2487                                cpuset_current_mems_allowed);
2488        put_mems_allowed();
2489out:
2490        return ret;
2491}
2492
2493#define K(x) ((x) << (PAGE_SHIFT-10))
2494
2495/*
2496 * Show free area list (used inside shift_scroll-lock stuff)
2497 * We also calculate the percentage fragmentation. We do this by counting the
2498 * memory on each free list with the exception of the first item on the list.
2499 * Suppresses nodes that are not allowed by current's cpuset if
2500 * SHOW_MEM_FILTER_NODES is passed.
2501 */
2502void __show_free_areas(unsigned int filter)
2503{
2504        int cpu;
2505        struct zone *zone;
2506
2507        for_each_populated_zone(zone) {
2508                if (skip_free_areas_zone(filter, zone))
2509                        continue;
2510                show_node(zone);
2511                printk("%s per-cpu:\n", zone->name);
2512
2513                for_each_online_cpu(cpu) {
2514                        struct per_cpu_pageset *pageset;
2515
2516                        pageset = per_cpu_ptr(zone->pageset, cpu);
2517
2518                        printk("CPU %4d: hi:%5d, btch:%4d usd:%4d\n",
2519                               cpu, pageset->pcp.high,
2520                               pageset->pcp.batch, pageset->pcp.count);
2521                }
2522        }
2523
2524        printk("active_anon:%lu inactive_anon:%lu isolated_anon:%lu\n"
2525                " active_file:%lu inactive_file:%lu isolated_file:%lu\n"
2526                " unevictable:%lu"
2527                " dirty:%lu writeback:%lu unstable:%lu\n"
2528                " free:%lu slab_reclaimable:%lu slab_unreclaimable:%lu\n"
2529                " mapped:%lu shmem:%lu pagetables:%lu bounce:%lu\n",
2530                global_page_state(NR_ACTIVE_ANON),
2531                global_page_state(NR_INACTIVE_ANON),
2532                global_page_state(NR_ISOLATED_ANON),
2533                global_page_state(NR_ACTIVE_FILE),
2534                global_page_state(NR_INACTIVE_FILE),
2535                global_page_state(NR_ISOLATED_FILE),
2536                global_page_state(NR_UNEVICTABLE),
2537                global_page_state(NR_FILE_DIRTY),
2538                global_page_state(NR_WRITEBACK),
2539                global_page_state(NR_UNSTABLE_NFS),
2540                global_page_state(NR_FREE_PAGES),
2541                global_page_state(NR_SLAB_RECLAIMABLE),
2542                global_page_state(NR_SLAB_UNRECLAIMABLE),
2543                global_page_state(NR_FILE_MAPPED),
2544                global_page_state(NR_SHMEM),
2545                global_page_state(NR_PAGETABLE),
2546                global_page_state(NR_BOUNCE));
2547
2548        for_each_populated_zone(zone) {
2549                int i;
2550
2551                if (skip_free_areas_zone(filter, zone))
2552                        continue;
2553                show_node(zone);
2554                printk("%s"
2555                        " free:%lukB"
2556                        " min:%lukB"
2557                        " low:%lukB"
2558                        " high:%lukB"
2559                        " active_anon:%lukB"
2560                        " inactive_anon:%lukB"
2561                        " active_file:%lukB"
2562                        " inactive_file:%lukB"
2563                        " unevictable:%lukB"
2564                        " isolated(anon):%lukB"
2565                        " isolated(file):%lukB"
2566                        " present:%lukB"
2567                        " mlocked:%lukB"
2568                        " dirty:%lukB"
2569                        " writeback:%lukB"
2570                        " mapped:%lukB"
2571                        " shmem:%lukB"
2572                        " slab_reclaimable:%lukB"
2573                        " slab_unreclaimable:%lukB"
2574                        " kernel_stack:%lukB"
2575                        " pagetables:%lukB"
2576                        " unstable:%lukB"
2577                        " bounce:%lukB"
2578                        " writeback_tmp:%lukB"
2579                        " pages_scanned:%lu"
2580                        " all_unreclaimable? %s"
2581                        "\n",
2582                        zone->name,
2583                        K(zone_page_state(zone, NR_FREE_PAGES)),
2584                        K(min_wmark_pages(zone)),
2585                        K(low_wmark_pages(zone)),
2586                        K(high_wmark_pages(zone)),
2587                        K(zone_page_state(zone, NR_ACTIVE_ANON)),
2588                        K(zone_page_state(zone, NR_INACTIVE_ANON)),
2589                        K(zone_page_state(zone, NR_ACTIVE_FILE)),
2590                        K(zone_page_state(zone, NR_INACTIVE_FILE)),
2591                        K(zone_page_state(zone, NR_UNEVICTABLE)),
2592                        K(zone_page_state(zone, NR_ISOLATED_ANON)),
2593                        K(zone_page_state(zone, NR_ISOLATED_FILE)),
2594                        K(zone->present_pages),
2595                        K(zone_page_state(zone, NR_MLOCK)),
2596                        K(zone_page_state(zone, NR_FILE_DIRTY)),
2597                        K(zone_page_state(zone, NR_WRITEBACK)),
2598                        K(zone_page_state(zone, NR_FILE_MAPPED)),
2599                        K(zone_page_state(zone, NR_SHMEM)),
2600                        K(zone_page_state(zone, NR_SLAB_RECLAIMABLE)),
2601                        K(zone_page_state(zone, NR_SLAB_UNRECLAIMABLE)),
2602                        zone_page_state(zone, NR_KERNEL_STACK) *
2603                                THREAD_SIZE / 1024,
2604                        K(zone_page_state(zone, NR_PAGETABLE)),
2605                        K(zone_page_state(zone, NR_UNSTABLE_NFS)),
2606                        K(zone_page_state(zone, NR_BOUNCE)),
2607                        K(zone_page_state(zone, NR_WRITEBACK_TEMP)),
2608                        zone->pages_scanned,
2609                        (zone->all_unreclaimable ? "yes" : "no")
2610                        );
2611                printk("lowmem_reserve[]:");
2612                for (i = 0; i < MAX_NR_ZONES; i++)
2613                        printk(" %lu", zone->lowmem_reserve[i]);
2614                printk("\n");
2615        }
2616
2617        for_each_populated_zone(zone) {
2618                unsigned long nr[MAX_ORDER], flags, order, total = 0;
2619
2620                if (skip_free_areas_zone(filter, zone))
2621                        continue;
2622                show_node(zone);
2623                printk("%s: ", zone->name);
2624
2625                spin_lock_irqsave(&zone->lock, flags);
2626                for (order = 0; order < MAX_ORDER; order++) {
2627                        nr[order] = zone->free_area[order].nr_free;
2628                        total += nr[order] << order;
2629                }
2630                spin_unlock_irqrestore(&zone->lock, flags);
2631                for (order = 0; order < MAX_ORDER; order++)
2632                        printk("%lu*%lukB ", nr[order], K(1UL) << order);
2633                printk("= %lukB\n", K(total));
2634        }
2635
2636        printk("%ld total pagecache pages\n", global_page_state(NR_FILE_PAGES));
2637
2638        show_swap_cache_info();
2639}
2640
2641void show_free_areas(void)
2642{
2643        __show_free_areas(0);
2644}
2645
2646static void zoneref_set_zone(struct zone *zone, struct zoneref *zoneref)
2647{
2648        zoneref->zone = zone;
2649        zoneref->zone_idx = zone_idx(zone);
2650}
2651
2652/*
2653 * Builds allocation fallback zone lists.
2654 *
2655 * Add all populated zones of a node to the zonelist.
2656 */
2657static int build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
2658                                int nr_zones, enum zone_type zone_type)
2659{
2660        struct zone *zone;
2661
2662        BUG_ON(zone_type >= MAX_NR_ZONES);
2663        zone_type++;
2664
2665        do {
2666                zone_type--;
2667                zone = pgdat->node_zones + zone_type;
2668                if (populated_zone(zone)) {
2669                        zoneref_set_zone(zone,
2670                                &zonelist->_zonerefs[nr_zones++]);
2671                        check_highest_zone(zone_type);
2672                }
2673
2674        } while (zone_type);
2675        return nr_zones;
2676}
2677
2678
2679/*
2680 *  zonelist_order:
2681 *  0 = automatic detection of better ordering.
2682 *  1 = order by ([node] distance, -zonetype)
2683 *  2 = order by (-zonetype, [node] distance)
2684 *
2685 *  If not NUMA, ZONELIST_ORDER_ZONE and ZONELIST_ORDER_NODE will create
2686 *  the same zonelist. So only NUMA can configure this param.
2687 */
2688#define ZONELIST_ORDER_DEFAULT  0
2689#define ZONELIST_ORDER_NODE     1
2690#define ZONELIST_ORDER_ZONE     2
2691
2692/* zonelist order in the kernel.
2693 * set_zonelist_order() will set this to NODE or ZONE.
2694 */
2695static int current_zonelist_order = ZONELIST_ORDER_DEFAULT;
2696static char zonelist_order_name[3][8] = {"Default", "Node", "Zone"};
2697
2698
2699#ifdef CONFIG_NUMA
2700/* The value user specified ....changed by config */
2701static int user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2702/* string for sysctl */
2703#define NUMA_ZONELIST_ORDER_LEN 16
2704char numa_zonelist_order[16] = "default";
2705
2706/*
2707 * interface for configure zonelist ordering.
2708 * command line option "numa_zonelist_order"
2709 *      = "[dD]efault   - default, automatic configuration.
2710 *      = "[nN]ode      - order by node locality, then by zone within node
2711 *      = "[zZ]one      - order by zone, then by locality within zone
2712 */
2713
2714static int __parse_numa_zonelist_order(char *s)
2715{
2716        if (*s == 'd' || *s == 'D') {
2717                user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2718        } else if (*s == 'n' || *s == 'N') {
2719                user_zonelist_order = ZONELIST_ORDER_NODE;
2720        } else if (*s == 'z' || *s == 'Z') {
2721                user_zonelist_order = ZONELIST_ORDER_ZONE;
2722        } else {
2723                printk(KERN_WARNING
2724                        "Ignoring invalid numa_zonelist_order value:  "
2725                        "%s\n", s);
2726                return -EINVAL;
2727        }
2728        return 0;
2729}
2730
2731static __init int setup_numa_zonelist_order(char *s)
2732{
2733        int ret;
2734
2735        if (!s)
2736                return 0;
2737
2738        ret = __parse_numa_zonelist_order(s);
2739        if (ret == 0)
2740                strlcpy(numa_zonelist_order, s, NUMA_ZONELIST_ORDER_LEN);
2741
2742        return ret;
2743}
2744early_param("numa_zonelist_order", setup_numa_zonelist_order);
2745
2746/*
2747 * sysctl handler for numa_zonelist_order
2748 */
2749int numa_zonelist_order_handler(ctl_table *table, int write,
2750                void __user *buffer, size_t *length,
2751                loff_t *ppos)
2752{
2753        char saved_string[NUMA_ZONELIST_ORDER_LEN];
2754        int ret;
2755        static DEFINE_MUTEX(zl_order_mutex);
2756
2757        mutex_lock(&zl_order_mutex);
2758        if (write)
2759                strcpy(saved_string, (char*)table->data);
2760        ret = proc_dostring(table, write, buffer, length, ppos);
2761        if (ret)
2762                goto out;
2763        if (write) {
2764                int oldval = user_zonelist_order;
2765                if (__parse_numa_zonelist_order((char*)table->data)) {
2766                        /*
2767                         * bogus value.  restore saved string
2768                         */
2769                        strncpy((char*)table->data, saved_string,
2770                                NUMA_ZONELIST_ORDER_LEN);
2771                        user_zonelist_order = oldval;
2772                } else if (oldval != user_zonelist_order) {
2773                        mutex_lock(&zonelists_mutex);
2774                        build_all_zonelists(NULL);
2775                        mutex_unlock(&zonelists_mutex);
2776                }
2777        }
2778out:
2779        mutex_unlock(&zl_order_mutex);
2780        return ret;
2781}
2782
2783
2784#define MAX_NODE_LOAD (nr_online_nodes)
2785static int node_load[MAX_NUMNODES];
2786
2787/**
2788 * find_next_best_node - find the next node that should appear in a given node's fallback list
2789 * @node: node whose fallback list we're appending
2790 * @used_node_mask: nodemask_t of already used nodes
2791 *
2792 * We use a number of factors to determine which is the next node that should
2793 * appear on a given node's fallback list.  The node should not have appeared
2794 * already in @node's fallback list, and it should be the next closest node
2795 * according to the distance array (which contains arbitrary distance values
2796 * from each node to each node in the system), and should also prefer nodes
2797 * with no CPUs, since presumably they'll have very little allocation pressure
2798 * on them otherwise.
2799 * It returns -1 if no node is found.
2800 */
2801static int find_next_best_node(int node, nodemask_t *used_node_mask)
2802{
2803        int n, val;
2804        int min_val = INT_MAX;
2805        int best_node = -1;
2806        const struct cpumask *tmp = cpumask_of_node(0);
2807
2808        /* Use the local node if we haven't already */
2809        if (!node_isset(node, *used_node_mask)) {
2810                node_set(node, *used_node_mask);
2811                return node;
2812        }
2813
2814        for_each_node_state(n, N_HIGH_MEMORY) {
2815
2816                /* Don't want a node to appear more than once */
2817                if (node_isset(n, *used_node_mask))
2818                        continue;
2819
2820                /* Use the distance array to find the distance */
2821                val = node_distance(node, n);
2822
2823                /* Penalize nodes under us ("prefer the next node") */
2824                val += (n < node);
2825
2826                /* Give preference to headless and unused nodes */
2827                tmp = cpumask_of_node(n);
2828                if (!cpumask_empty(tmp))
2829                        val += PENALTY_FOR_NODE_WITH_CPUS;
2830
2831                /* Slight preference for less loaded node */
2832                val *= (MAX_NODE_LOAD*MAX_NUMNODES);
2833                val += node_load[n];
2834
2835                if (val < min_val) {
2836                        min_val = val;
2837                        best_node = n;
2838                }
2839        }
2840
2841        if (best_node >= 0)
2842                node_set(best_node, *used_node_mask);
2843
2844        return best_node;
2845}
2846
2847
2848/*
2849 * Build zonelists ordered by node and zones within node.
2850 * This results in maximum locality--normal zone overflows into local
2851 * DMA zone, if any--but risks exhausting DMA zone.
2852 */
2853static void build_zonelists_in_node_order(pg_data_t *pgdat, int node)
2854{
2855        int j;
2856        struct zonelist *zonelist;
2857
2858        zonelist = &pgdat->node_zonelists[0];
2859        for (j = 0; zonelist->_zonerefs[j].zone != NULL; j++)
2860                ;
2861        j = build_zonelists_node(NODE_DATA(node), zonelist, j,
2862                                                        MAX_NR_ZONES - 1);
2863        zonelist->_zonerefs[j].zone = NULL;
2864        zonelist->_zonerefs[j].zone_idx = 0;
2865}
2866
2867/*
2868 * Build gfp_thisnode zonelists
2869 */
2870static void build_thisnode_zonelists(pg_data_t *pgdat)
2871{
2872        int j;
2873        struct zonelist *zonelist;
2874
2875        zonelist = &pgdat->node_zonelists[1];
2876        j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
2877        zonelist->_zonerefs[j].zone = NULL;
2878        zonelist->_zonerefs[j].zone_idx = 0;
2879}
2880
2881/*
2882 * Build zonelists ordered by zone and nodes within zones.
2883 * This results in conserving DMA zone[s] until all Normal memory is
2884 * exhausted, but results in overflowing to remote node while memory
2885 * may still exist in local DMA zone.
2886 */
2887static int node_order[MAX_NUMNODES];
2888
2889static void build_zonelists_in_zone_order(pg_data_t *pgdat, int nr_nodes)
2890{
2891        int pos, j, node;
2892        int zone_type;          /* needs to be signed */
2893        struct zone *z;
2894        struct zonelist *zonelist;
2895
2896        zonelist = &pgdat->node_zonelists[0];
2897        pos = 0;
2898        for (zone_type = MAX_NR_ZONES - 1; zone_type >= 0; zone_type--) {
2899                for (j = 0; j < nr_nodes; j++) {
2900                        node = node_order[j];
2901                        z = &NODE_DATA(node)->node_zones[zone_type];
2902                        if (populated_zone(z)) {
2903                                zoneref_set_zone(z,
2904                                        &zonelist->_zonerefs[pos++]);
2905                                check_highest_zone(zone_type);
2906                        }
2907                }
2908        }
2909        zonelist->_zonerefs[pos].zone = NULL;
2910        zonelist->_zonerefs[pos].zone_idx = 0;
2911}
2912
2913static int default_zonelist_order(void)
2914{
2915        int nid, zone_type;
2916        unsigned long low_kmem_size,total_size;
2917        struct zone *z;
2918        int average_size;
2919        /*
2920         * ZONE_DMA and ZONE_DMA32 can be very small area in the system.
2921         * If they are really small and used heavily, the system can fall
2922         * into OOM very easily.
2923         * This function detect ZONE_DMA/DMA32 size and configures zone order.
2924         */
2925        /* Is there ZONE_NORMAL ? (ex. ppc has only DMA zone..) */
2926        low_kmem_size = 0;
2927        total_size = 0;
2928        for_each_online_node(nid) {
2929                for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
2930                        z = &NODE_DATA(nid)->node_zones[zone_type];
2931                        if (populated_zone(z)) {
2932                                if (zone_type < ZONE_NORMAL)
2933                                        low_kmem_size += z->present_pages;
2934                                total_size += z->present_pages;
2935                        } else if (zone_type == ZONE_NORMAL) {
2936                                /*
2937                                 * If any node has only lowmem, then node order
2938                                 * is preferred to allow kernel allocations
2939                                 * locally; otherwise, they can easily infringe
2940                                 * on other nodes when there is an abundance of
2941                                 * lowmem available to allocate from.
2942                                 */
2943                                return ZONELIST_ORDER_NODE;
2944                        }
2945                }
2946        }
2947        if (!low_kmem_size ||  /* there are no DMA area. */
2948            low_kmem_size > total_size/2) /* DMA/DMA32 is big. */
2949                return ZONELIST_ORDER_NODE;
2950        /*
2951         * look into each node's config.
2952         * If there is a node whose DMA/DMA32 memory is very big area on
2953         * local memory, NODE_ORDER may be suitable.
2954         */
2955        average_size = total_size /
2956                                (nodes_weight(node_states[N_HIGH_MEMORY]) + 1);
2957        for_each_online_node(nid) {
2958                low_kmem_size = 0;
2959                total_size = 0;
2960                for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
2961                        z = &NODE_DATA(nid)->node_zones[zone_type];
2962                        if (populated_zone(z)) {
2963                                if (zone_type < ZONE_NORMAL)
2964                                        low_kmem_size += z->present_pages;
2965                                total_size += z->present_pages;
2966                        }
2967                }
2968                if (low_kmem_size &&
2969                    total_size > average_size && /* ignore small node */
2970                    low_kmem_size > total_size * 70/100)
2971                        return ZONELIST_ORDER_NODE;
2972        }
2973        return ZONELIST_ORDER_ZONE;
2974}
2975
2976static void set_zonelist_order(void)
2977{
2978        if (user_zonelist_order == ZONELIST_ORDER_DEFAULT)
2979                current_zonelist_order = default_zonelist_order();
2980        else
2981                current_zonelist_order = user_zonelist_order;
2982}
2983
2984static void build_zonelists(pg_data_t *pgdat)
2985{
2986        int j, node, load;
2987        enum zone_type i;
2988        nodemask_t used_mask;
2989        int local_node, prev_node;
2990        struct zonelist *zonelist;
2991        int order = current_zonelist_order;
2992
2993        /* initialize zonelists */
2994        for (i = 0; i < MAX_ZONELISTS; i++) {
2995                zonelist = pgdat->node_zonelists + i;
2996                zonelist->_zonerefs[0].zone = NULL;
2997                zonelist->_zonerefs[0].zone_idx = 0;
2998        }
2999
3000        /* NUMA-aware ordering of nodes */
3001        local_node = pgdat->node_id;
3002        load = nr_online_nodes;
3003        prev_node = local_node;
3004        nodes_clear(used_mask);
3005
3006        memset(node_order, 0, sizeof(node_order));
3007        j = 0;
3008
3009        while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
3010                int distance = node_distance(local_node, node);
3011
3012                /*
3013                 * If another node is sufficiently far away then it is better
3014                 * to reclaim pages in a zone before going off node.
3015                 */
3016                if (distance > RECLAIM_DISTANCE)
3017                        zone_reclaim_mode = 1;
3018
3019                /*
3020                 * We don't want to pressure a particular node.
3021                 * So adding penalty to the first node in same
3022                 * distance group to make it round-robin.
3023                 */
3024                if (distance != node_distance(local_node, prev_node))
3025                        node_load[node] = load;
3026
3027                prev_node = node;
3028                load--;
3029                if (order == ZONELIST_ORDER_NODE)
3030                        build_zonelists_in_node_order(pgdat, node);
3031                else
3032                        node_order[j++] = node; /* remember order */
3033        }
3034
3035        if (order == ZONELIST_ORDER_ZONE) {
3036                /* calculate node order -- i.e., DMA last! */
3037                build_zonelists_in_zone_order(pgdat, j);
3038        }
3039
3040        build_thisnode_zonelists(pgdat);
3041}
3042
3043/* Construct the zonelist performance cache - see further mmzone.h */
3044static void build_zonelist_cache(pg_data_t *pgdat)
3045{
3046        struct zonelist *zonelist;
3047        struct zonelist_cache *zlc;
3048        struct zoneref *z;
3049
3050        zonelist = &pgdat->node_zonelists[0];
3051        zonelist->zlcache_ptr = zlc = &zonelist->zlcache;
3052        bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
3053        for (z = zonelist->_zonerefs; z->zone; z++)
3054                zlc->z_to_n[z - zonelist->_zonerefs] = zonelist_node_idx(z);
3055}
3056
3057#ifdef CONFIG_HAVE_MEMORYLESS_NODES
3058/*
3059 * Return node id of node used for "local" allocations.
3060 * I.e., first node id of first zone in arg node's generic zonelist.
3061 * Used for initializing percpu 'numa_mem', which is used primarily
3062 * for kernel allocations, so use GFP_KERNEL flags to locate zonelist.
3063 */
3064int local_memory_node(int node)
3065{
3066        struct zone *zone;
3067
3068        (void)first_zones_zonelist(node_zonelist(node, GFP_KERNEL),
3069                                   gfp_zone(GFP_KERNEL),
3070                                   NULL,
3071                                   &zone);
3072        return zone->node;
3073}
3074#endif
3075
3076#else   /* CONFIG_NUMA */
3077
3078static void set_zonelist_order(void)
3079{
3080        current_zonelist_order = ZONELIST_ORDER_ZONE;
3081}
3082
3083static void build_zonelists(pg_data_t *pgdat)
3084{
3085        int node, local_node;
3086        enum zone_type j;
3087        struct zonelist *zonelist;
3088
3089        local_node = pgdat->node_id;
3090
3091        zonelist = &pgdat->node_zonelists[0];
3092        j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
3093
3094        /*
3095         * Now we build the zonelist so that it contains the zones
3096         * of all the other nodes.
3097         * We don't want to pressure a particular node, so when
3098         * building the zones for node N, we make sure that the
3099         * zones coming right after the local ones are those from
3100         * node N+1 (modulo N)
3101         */
3102        for (node = local_node + 1; node < MAX_NUMNODES; node++) {
3103                if (!node_online(node))
3104                        continue;
3105                j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3106                                                        MAX_NR_ZONES - 1);
3107        }
3108        for (node = 0; node < local_node; node++) {
3109                if (!node_online(node))
3110                        continue;
3111                j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3112                                                        MAX_NR_ZONES - 1);
3113        }
3114
3115        zonelist->_zonerefs[j].zone = NULL;
3116        zonelist->_zonerefs[j].zone_idx = 0;
3117}
3118
3119/* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
3120static void build_zonelist_cache(pg_data_t *pgdat)
3121{
3122        pgdat->node_zonelists[0].zlcache_ptr = NULL;
3123}
3124
3125#endif  /* CONFIG_NUMA */
3126
3127/*
3128 * Boot pageset table. One per cpu which is going to be used for all
3129 * zones and all nodes. The parameters will be set in such a way
3130 * that an item put on a list will immediately be handed over to
3131 * the buddy list. This is safe since pageset manipulation is done
3132 * with interrupts disabled.
3133 *
3134 * The boot_pagesets must be kept even after bootup is complete for
3135 * unused processors and/or zones. They do play a role for bootstrapping
3136 * hotplugged processors.
3137 *
3138 * zoneinfo_show() and maybe other functions do
3139 * not check if the processor is online before following the pageset pointer.
3140 * Other parts of the kernel may not check if the zone is available.
3141 */
3142static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch);
3143static DEFINE_PER_CPU(struct per_cpu_pageset, boot_pageset);
3144static void setup_zone_pageset(struct zone *zone);
3145
3146/*
3147 * Global mutex to protect against size modification of zonelists
3148 * as well as to serialize pageset setup for the new populated zone.
3149 */
3150DEFINE_MUTEX(zonelists_mutex);
3151
3152/* return values int ....just for stop_machine() */
3153static __init_refok int __build_all_zonelists(void *data)
3154{
3155        int nid;
3156        int cpu;
3157
3158#ifdef CONFIG_NUMA
3159        memset(node_load, 0, sizeof(node_load));
3160#endif
3161        for_each_online_node(nid) {
3162                pg_data_t *pgdat = NODE_DATA(nid);
3163
3164                build_zonelists(pgdat);
3165                build_zonelist_cache(pgdat);
3166        }
3167
3168        /*
3169         * Initialize the boot_pagesets that are going to be used
3170         * for bootstrapping processors. The real pagesets for
3171         * each zone will be allocated later when the per cpu
3172         * allocator is available.
3173         *
3174         * boot_pagesets are used also for bootstrapping offline
3175         * cpus if the system is already booted because the pagesets
3176         * are needed to initialize allocators on a specific cpu too.
3177         * F.e. the percpu allocator needs the page allocator which
3178         * needs the percpu allocator in order to allocate its pagesets
3179         * (a chicken-egg dilemma).
3180         */
3181        for_each_possible_cpu(cpu) {
3182                setup_pageset(&per_cpu(boot_pageset, cpu), 0);
3183
3184#ifdef CONFIG_HAVE_MEMORYLESS_NODES
3185                /*
3186                 * We now know the "local memory node" for each node--
3187                 * i.e., the node of the first zone in the generic zonelist.
3188                 * Set up numa_mem percpu variable for on-line cpus.  During
3189                 * boot, only the boot cpu should be on-line;  we'll init the
3190                 * secondary cpus' numa_mem as they come on-line.  During
3191                 * node/memory hotplug, we'll fixup all on-line cpus.
3192                 */
3193                if (cpu_online(cpu))
3194                        set_cpu_numa_mem(cpu, local_memory_node(cpu_to_node(cpu)));
3195#endif
3196        }
3197
3198        return 0;
3199}
3200
3201/*
3202 * Called with zonelists_mutex held always
3203 * unless system_state == SYSTEM_BOOTING.
3204 */
3205void __ref build_all_zonelists(void *data)
3206{
3207        set_zonelist_order();
3208
3209        if (system_state == SYSTEM_BOOTING) {
3210                __build_all_zonelists(NULL);
3211                mminit_verify_zonelist();
3212                cpuset_init_current_mems_allowed();
3213        } else {
3214                /* we have to stop all cpus to guarantee there is no user
3215                   of zonelist */
3216#ifdef CONFIG_MEMORY_HOTPLUG
3217                if (data)
3218                        setup_zone_pageset((struct zone *)data);
3219#endif
3220                stop_machine(__build_all_zonelists, NULL, NULL);
3221                /* cpuset refresh routine should be here */
3222        }
3223        vm_total_pages = nr_free_pagecache_pages();
3224        /*
3225         * Disable grouping by mobility if the number of pages in the
3226         * system is too low to allow the mechanism to work. It would be
3227         * more accurate, but expensive to check per-zone. This check is
3228         * made on memory-hotadd so a system can start with mobility
3229         * disabled and enable it later
3230         */
3231        if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
3232                page_group_by_mobility_disabled = 1;
3233        else
3234                page_group_by_mobility_disabled = 0;
3235
3236        printk("Built %i zonelists in %s order, mobility grouping %s.  "
3237                "Total pages: %ld\n",
3238                        nr_online_nodes,
3239                        zonelist_order_name[current_zonelist_order],
3240                        page_group_by_mobility_disabled ? "off" : "on",
3241                        vm_total_pages);
3242#ifdef CONFIG_NUMA
3243        printk("Policy zone: %s\n", zone_names[policy_zone]);
3244#endif
3245}
3246
3247/*
3248 * Helper functions to size the waitqueue hash table.
3249 * Essentially these want to choose hash table sizes sufficiently
3250 * large so that collisions trying to wait on pages are rare.
3251 * But in fact, the number of active page waitqueues on typical
3252 * systems is ridiculously low, less than 200. So this is even
3253 * conservative, even though it seems large.
3254 *
3255 * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
3256 * waitqueues, i.e. the size of the waitq table given the number of pages.
3257 */
3258#define PAGES_PER_WAITQUEUE     256
3259
3260#ifndef CONFIG_MEMORY_HOTPLUG
3261static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
3262{
3263        unsigned long size = 1;
3264
3265        pages /= PAGES_PER_WAITQUEUE;
3266
3267        while (size < pages)
3268                size <<= 1;
3269
3270        /*
3271         * Once we have dozens or even hundreds of threads sleeping
3272         * on IO we've got bigger problems than wait queue collision.
3273         * Limit the size of the wait table to a reasonable size.
3274         */
3275        size = min(size, 4096UL);
3276
3277        return max(size, 4UL);
3278}
3279#else
3280/*
3281 * A zone's size might be changed by hot-add, so it is not possible to determine
3282 * a suitable size for its wait_table.  So we use the maximum size now.
3283 *
3284 * The max wait table size = 4096 x sizeof(wait_queue_head_t).   ie:
3285 *
3286 *    i386 (preemption config)    : 4096 x 16 = 64Kbyte.
3287 *    ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte.
3288 *    ia64, x86-64 (preemption)   : 4096 x 24 = 96Kbyte.
3289 *
3290 * The maximum entries are prepared when a zone's memory is (512K + 256) pages
3291 * or more by the traditional way. (See above).  It equals:
3292 *
3293 *    i386, x86-64, powerpc(4K page size) : =  ( 2G + 1M)byte.
3294 *    ia64(16K page size)                 : =  ( 8G + 4M)byte.
3295 *    powerpc (64K page size)             : =  (32G +16M)byte.
3296 */
3297static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
3298{
3299        return 4096UL;
3300}
3301#endif
3302
3303/*
3304 * This is an integer logarithm so that shifts can be used later
3305 * to extract the more random high bits from the multiplicative
3306 * hash function before the remainder is taken.
3307 */
3308static inline unsigned long wait_table_bits(unsigned long size)
3309{
3310        return ffz(~size);
3311}
3312
3313#define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
3314
3315/*
3316 * Mark a number of pageblocks as MIGRATE_RESERVE. The number
3317 * of blocks reserved is based on min_wmark_pages(zone). The memory within
3318 * the reserve will tend to store contiguous free pages. Setting min_free_kbytes
3319 * higher will lead to a bigger reserve which will get freed as contiguous
3320 * blocks as reclaim kicks in
3321 */
3322static void setup_zone_migrate_reserve(struct zone *zone)
3323{
3324        unsigned long start_pfn, pfn, end_pfn;
3325        struct page *page;
3326        unsigned long block_migratetype;
3327        int reserve;
3328
3329        /* Get the start pfn, end pfn and the number of blocks to reserve */
3330        start_pfn = zone->zone_start_pfn;
3331        end_pfn = start_pfn + zone->spanned_pages;
3332        reserve = roundup(min_wmark_pages(zone), pageblock_nr_pages) >>
3333                                                        pageblock_order;
3334
3335        /*
3336         * Reserve blocks are generally in place to help high-order atomic
3337         * allocations that are short-lived. A min_free_kbytes value that
3338         * would result in more than 2 reserve blocks for atomic allocations
3339         * is assumed to be in place to help anti-fragmentation for the
3340         * future allocation of hugepages at runtime.
3341         */
3342        reserve = min(2, reserve);
3343
3344        for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
3345                if (!pfn_valid(pfn))
3346                        continue;
3347                page = pfn_to_page(pfn);
3348
3349                /* Watch out for overlapping nodes */
3350                if (page_to_nid(page) != zone_to_nid(zone))
3351                        continue;
3352
3353                /* Blocks with reserved pages will never free, skip them. */
3354                if (PageReserved(page))
3355                        continue;
3356
3357                block_migratetype = get_pageblock_migratetype(page);
3358
3359                /* If this block is reserved, account for it */
3360                if (reserve > 0 && block_migratetype == MIGRATE_RESERVE) {
3361                        reserve--;
3362                        continue;
3363                }
3364
3365                /* Suitable for reserving if this block is movable */
3366                if (reserve > 0 && block_migratetype == MIGRATE_MOVABLE) {
3367                        set_pageblock_migratetype(page, MIGRATE_RESERVE);
3368                        move_freepages_block(zone, page, MIGRATE_RESERVE);
3369                        reserve--;
3370                        continue;
3371                }
3372
3373                /*
3374                 * If the reserve is met and this is a previous reserved block,
3375                 * take it back
3376                 */
3377                if (block_migratetype == MIGRATE_RESERVE) {
3378                        set_pageblock_migratetype(page, MIGRATE_MOVABLE);
3379                        move_freepages_block(zone, page, MIGRATE_MOVABLE);
3380                }
3381        }
3382}
3383
3384/*
3385 * Initially all pages are reserved - free ones are freed
3386 * up by free_all_bootmem() once the early boot process is
3387 * done. Non-atomic initialization, single-pass.
3388 */
3389void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
3390                unsigned long start_pfn, enum memmap_context context)
3391{
3392        struct page *page;
3393        unsigned long end_pfn = start_pfn + size;
3394        unsigned long pfn;
3395        struct zone *z;
3396
3397        if (highest_memmap_pfn < end_pfn - 1)
3398                highest_memmap_pfn = end_pfn - 1;
3399
3400        z = &NODE_DATA(nid)->node_zones[zone];
3401        for (pfn = start_pfn; pfn < end_pfn; pfn++) {
3402                /*
3403                 * There can be holes in boot-time mem_map[]s
3404                 * handed to this function.  They do not
3405                 * exist on hotplugged memory.
3406                 */
3407                if (context == MEMMAP_EARLY) {
3408                        if (!early_pfn_valid(pfn))
3409                                continue;
3410                        if (!early_pfn_in_nid(pfn, nid))
3411                                continue;
3412                }
3413                page = pfn_to_page(pfn);
3414                set_page_links(page, zone, nid, pfn);
3415                mminit_verify_page_links(page, zone, nid, pfn);
3416                init_page_count(page);
3417                reset_page_mapcount(page);
3418                SetPageReserved(page);
3419                /*
3420                 * Mark the block movable so that blocks are reserved for
3421                 * movable at startup. This will force kernel allocations
3422                 * to reserve their blocks rather than leaking throughout
3423                 * the address space during boot when many long-lived
3424                 * kernel allocations are made. Later some blocks near
3425                 * the start are marked MIGRATE_RESERVE by
3426                 * setup_zone_migrate_reserve()
3427                 *
3428                 * bitmap is created for zone's valid pfn range. but memmap
3429                 * can be created for invalid pages (for alignment)
3430                 * check here not to call set_pageblock_migratetype() against
3431                 * pfn out of zone.
3432                 */
3433                if ((z->zone_start_pfn <= pfn)
3434                    && (pfn < z->zone_start_pfn + z->spanned_pages)
3435                    && !(pfn & (pageblock_nr_pages - 1)))
3436                        set_pageblock_migratetype(page, MIGRATE_MOVABLE);
3437
3438                INIT_LIST_HEAD(&page->lru);
3439#ifdef WANT_PAGE_VIRTUAL
3440                /* The shift won't overflow because ZONE_NORMAL is below 4G. */
3441                if (!is_highmem_idx(zone))
3442                        set_page_address(page, __va(pfn << PAGE_SHIFT));
3443#endif
3444        }
3445}
3446
3447static void __meminit zone_init_free_lists(struct zone *zone)
3448{
3449        int order, t;
3450        for_each_migratetype_order(order, t) {
3451                INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);
3452                zone->free_area[order].nr_free = 0;
3453        }
3454}
3455
3456#ifndef __HAVE_ARCH_MEMMAP_INIT
3457#define memmap_init(size, nid, zone, start_pfn) \
3458        memmap_init_zone((size), (nid), (zone), (start_pfn), MEMMAP_EARLY)
3459#endif
3460
3461static int zone_batchsize(struct zone *zone)
3462{
3463#ifdef CONFIG_MMU
3464        int batch;
3465
3466        /*
3467         * The per-cpu-pages pools are set to around 1000th of the
3468         * size of the zone.  But no more than 1/2 of a meg.
3469         *
3470         * OK, so we don't know how big the cache is.  So guess.
3471         */
3472        batch = zone->present_pages / 1024;
3473        if (batch * PAGE_SIZE > 512 * 1024)
3474                batch = (512 * 1024) / PAGE_SIZE;
3475        batch /= 4;             /* We effectively *= 4 below */
3476        if (batch < 1)
3477                batch = 1;
3478
3479        /*
3480         * Clamp the batch to a 2^n - 1 value. Having a power
3481         * of 2 value was found to be more likely to have
3482         * suboptimal cache aliasing properties in some cases.
3483         *
3484         * For example if 2 tasks are alternately allocating
3485         * batches of pages, one task can end up with a lot
3486         * of pages of one half of the possible page colors
3487         * and the other with pages of the other colors.
3488         */
3489        batch = rounddown_pow_of_two(batch + batch/2) - 1;
3490
3491        return batch;
3492
3493#else
3494        /* The deferral and batching of frees should be suppressed under NOMMU
3495         * conditions.
3496         *
3497         * The problem is that NOMMU needs to be able to allocate large chunks
3498         * of contiguous memory as there's no hardware page translation to
3499         * assemble apparent contiguous memory from discontiguous pages.
3500         *
3501         * Queueing large contiguous runs of pages for batching, however,
3502         * causes the pages to actually be freed in smaller chunks.  As there
3503         * can be a significant delay between the individual batches being
3504         * recycled, this leads to the once large chunks of space being
3505         * fragmented and becoming unavailable for high-order allocations.
3506         */
3507        return 0;
3508#endif
3509}
3510
3511static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
3512{
3513        struct per_cpu_pages *pcp;
3514        int migratetype;
3515
3516        memset(p, 0, sizeof(*p));
3517
3518        pcp = &p->pcp;
3519        pcp->count = 0;
3520        pcp->high = 6 * batch;
3521        pcp->batch = max(1UL, 1 * batch);
3522        for (migratetype = 0; migratetype < MIGRATE_PCPTYPES; migratetype++)
3523                INIT_LIST_HEAD(&pcp->lists[migratetype]);
3524}
3525
3526/*
3527 * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist
3528 * to the value high for the pageset p.
3529 */
3530
3531static void setup_pagelist_highmark(struct per_cpu_pageset *p,
3532                                unsigned long high)
3533{
3534        struct per_cpu_pages *pcp;
3535
3536        pcp = &p->pcp;
3537        pcp->high = high;
3538        pcp->batch = max(1UL, high/4);
3539        if ((high/4) > (PAGE_SHIFT * 8))
3540                pcp->batch = PAGE_SHIFT * 8;
3541}
3542
3543static __meminit void setup_zone_pageset(struct zone *zone)
3544{
3545        int cpu;
3546
3547        zone->pageset = alloc_percpu(struct per_cpu_pageset);
3548
3549        for_each_possible_cpu(cpu) {
3550                struct per_cpu_pageset *pcp = per_cpu_ptr(zone->pageset, cpu);
3551
3552                setup_pageset(pcp, zone_batchsize(zone));
3553
3554                if (percpu_pagelist_fraction)
3555                        setup_pagelist_highmark(pcp,
3556                                (zone->present_pages /
3557                                        percpu_pagelist_fraction));
3558        }
3559}
3560
3561/*
3562 * Allocate per cpu pagesets and initialize them.
3563 * Before this call only boot pagesets were available.
3564 */
3565void __init setup_per_cpu_pageset(void)
3566{
3567        struct zone *zone;
3568
3569        for_each_populated_zone(zone)
3570                setup_zone_pageset(zone);
3571}
3572
3573static noinline __init_refok
3574int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages)
3575{
3576        int i;
3577        struct pglist_data *pgdat = zone->zone_pgdat;
3578        size_t alloc_size;
3579
3580        /*
3581         * The per-page waitqueue mechanism uses hashed waitqueues
3582         * per zone.
3583         */
3584        zone->wait_table_hash_nr_entries =
3585                 wait_table_hash_nr_entries(zone_size_pages);
3586        zone->wait_table_bits =
3587                wait_table_bits(zone->wait_table_hash_nr_entries);
3588        alloc_size = zone->wait_table_hash_nr_entries
3589                                        * sizeof(wait_queue_head_t);
3590
3591        if (!slab_is_available()) {
3592                zone->wait_table = (wait_queue_head_t *)
3593                        alloc_bootmem_node_nopanic(pgdat, alloc_size);
3594        } else {
3595                /*
3596                 * This case means that a zone whose size was 0 gets new memory
3597                 * via memory hot-add.
3598                 * But it may be the case that a new node was hot-added.  In
3599                 * this case vmalloc() will not be able to use this new node's
3600                 * memory - this wait_table must be initialized to use this new
3601                 * node itself as well.
3602                 * To use this new node's memory, further consideration will be
3603                 * necessary.
3604                 */
3605                zone->wait_table = vmalloc(alloc_size);
3606        }
3607        if (!zone->wait_table)
3608                return -ENOMEM;
3609
3610        for(i = 0; i < zone->wait_table_hash_nr_entries; ++i)
3611                init_waitqueue_head(zone->wait_table + i);
3612
3613        return 0;
3614}
3615
3616static int __zone_pcp_update(void *data)
3617{
3618        struct zone *zone = data;
3619        int cpu;
3620        unsigned long batch = zone_batchsize(zone), flags;
3621
3622        for_each_possible_cpu(cpu) {
3623                struct per_cpu_pageset *pset;
3624                struct per_cpu_pages *pcp;
3625
3626                pset = per_cpu_ptr(zone->pageset, cpu);
3627                pcp = &pset->pcp;
3628
3629                local_irq_save(flags);
3630                free_pcppages_bulk(zone, pcp->count, pcp);
3631                setup_pageset(pset, batch);
3632                local_irq_restore(flags);
3633        }
3634        return 0;
3635}
3636
3637void zone_pcp_update(struct zone *zone)
3638{
3639        stop_machine(__zone_pcp_update, zone, NULL);
3640}
3641
3642static __meminit void zone_pcp_init(struct zone *zone)
3643{
3644        /*
3645         * per cpu subsystem is not up at this point. The following code
3646         * relies on the ability of the linker to provide the
3647         * offset of a (static) per cpu variable into the per cpu area.
3648         */
3649        zone->pageset = &boot_pageset;
3650
3651        if (zone->present_pages)
3652                printk(KERN_DEBUG "  %s zone: %lu pages, LIFO batch:%u\n",
3653                        zone->name, zone->present_pages,
3654                                         zone_batchsize(zone));
3655}
3656
3657__meminit int init_currently_empty_zone(struct zone *zone,
3658                                        unsigned long zone_start_pfn,
3659                                        unsigned long size,
3660                                        enum memmap_context context)
3661{
3662        struct pglist_data *pgdat = zone->zone_pgdat;
3663        int ret;
3664        ret = zone_wait_table_init(zone, size);
3665        if (ret)
3666                return ret;
3667        pgdat->nr_zones = zone_idx(zone) + 1;
3668
3669        zone->zone_start_pfn = zone_start_pfn;
3670
3671        mminit_dprintk(MMINIT_TRACE, "memmap_init",
3672                        "Initialising map node %d zone %lu pfns %lu -> %lu\n",
3673                        pgdat->node_id,
3674                        (unsigned long)zone_idx(zone),
3675                        zone_start_pfn, (zone_start_pfn + size));
3676
3677        zone_init_free_lists(zone);
3678
3679        return 0;
3680}
3681
3682#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
3683/*
3684 * Basic iterator support. Return the first range of PFNs for a node
3685 * Note: nid == MAX_NUMNODES returns first region regardless of node
3686 */
3687static int __meminit first_active_region_index_in_nid(int nid)
3688{
3689        int i;
3690
3691        for (i = 0; i < nr_nodemap_entries; i++)
3692                if (nid == MAX_NUMNODES || early_node_map[i].nid == nid)
3693                        return i;
3694
3695        return -1;
3696}
3697
3698/*
3699 * Basic iterator support. Return the next active range of PFNs for a node
3700 * Note: nid == MAX_NUMNODES returns next region regardless of node
3701 */
3702static int __meminit next_active_region_index_in_nid(int index, int nid)
3703{
3704        for (index = index + 1; index < nr_nodemap_entries; index++)
3705                if (nid == MAX_NUMNODES || early_node_map[index].nid == nid)
3706                        return index;
3707
3708        return -1;
3709}
3710
3711#ifndef CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID
3712/*
3713 * Required by SPARSEMEM. Given a PFN, return what node the PFN is on.
3714 * Architectures may implement their own version but if add_active_range()
3715 * was used and there are no special requirements, this is a convenient
3716 * alternative
3717 */
3718int __meminit __early_pfn_to_nid(unsigned long pfn)
3719{
3720        int i;
3721
3722        for (i = 0; i < nr_nodemap_entries; i++) {
3723                unsigned long start_pfn = early_node_map[i].start_pfn;
3724                unsigned long end_pfn = early_node_map[i].end_pfn;
3725
3726                if (start_pfn <= pfn && pfn < end_pfn)
3727                        return early_node_map[i].nid;
3728        }
3729        /* This is a memory hole */
3730        return -1;
3731}
3732#endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */
3733
3734int __meminit early_pfn_to_nid(unsigned long pfn)
3735{
3736        int nid;
3737
3738        nid = __early_pfn_to_nid(pfn);
3739        if (nid >= 0)
3740                return nid;
3741        /* just returns 0 */
3742        return 0;
3743}
3744
3745#ifdef CONFIG_NODES_SPAN_OTHER_NODES
3746bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
3747{
3748        int nid;
3749
3750        nid = __early_pfn_to_nid(pfn);
3751        if (nid >= 0 && nid != node)
3752                return false;
3753        return true;
3754}
3755#endif
3756
3757/* Basic iterator support to walk early_node_map[] */
3758#define for_each_active_range_index_in_nid(i, nid) \
3759        for (i = first_active_region_index_in_nid(nid); i != -1; \
3760                                i = next_active_region_index_in_nid(i, nid))
3761
3762/**
3763 * free_bootmem_with_active_regions - Call free_bootmem_node for each active range
3764 * @nid: The node to free memory on. If MAX_NUMNODES, all nodes are freed.
3765 * @max_low_pfn: The highest PFN that will be passed to free_bootmem_node
3766 *
3767 * If an architecture guarantees that all ranges registered with
3768 * add_active_ranges() contain no holes and may be freed, this
3769 * this function may be used instead of calling free_bootmem() manually.
3770 */
3771void __init free_bootmem_with_active_regions(int nid,
3772                                                unsigned long max_low_pfn)
3773{
3774        int i;
3775
3776        for_each_active_range_index_in_nid(i, nid) {
3777                unsigned long size_pages = 0;
3778                unsigned long end_pfn = early_node_map[i].end_pfn;
3779
3780                if (early_node_map[i].start_pfn >= max_low_pfn)
3781                        continue;
3782
3783                if (end_pfn > max_low_pfn)
3784                        end_pfn = max_low_pfn;
3785
3786                size_pages = end_pfn - early_node_map[i].start_pfn;
3787                free_bootmem_node(NODE_DATA(early_node_map[i].nid),
3788                                PFN_PHYS(early_node_map[i].start_pfn),
3789                                size_pages << PAGE_SHIFT);
3790        }
3791}
3792
3793#ifdef CONFIG_HAVE_MEMBLOCK
3794/*
3795 * Basic iterator support. Return the last range of PFNs for a node
3796 * Note: nid == MAX_NUMNODES returns last region regardless of node
3797 */
3798static int __meminit last_active_region_index_in_nid(int nid)
3799{
3800        int i;
3801
3802        for (i = nr_nodemap_entries - 1; i >= 0; i--)
3803                if (nid == MAX_NUMNODES || early_node_map[i].nid == nid)
3804                        return i;
3805
3806        return -1;
3807}
3808
3809/*
3810 * Basic iterator support. Return the previous active range of PFNs for a node
3811 * Note: nid == MAX_NUMNODES returns next region regardless of node
3812 */
3813static int __meminit previous_active_region_index_in_nid(int index, int nid)
3814{
3815        for (index = index - 1; index >= 0; index--)
3816                if (nid == MAX_NUMNODES || early_node_map[index].nid == nid)
3817                        return index;
3818
3819        return -1;
3820}
3821
3822#define for_each_active_range_index_in_nid_reverse(i, nid) \
3823        for (i = last_active_region_index_in_nid(nid); i != -1; \
3824                                i = previous_active_region_index_in_nid(i, nid))
3825
3826u64 __init find_memory_core_early(int nid, u64 size, u64 align,
3827                                        u64 goal, u64 limit)
3828{
3829        int i;
3830
3831        /* Need to go over early_node_map to find out good range for node */
3832        for_each_active_range_index_in_nid_reverse(i, nid) {
3833                u64 addr;
3834                u64 ei_start, ei_last;
3835                u64 final_start, final_end;
3836
3837                ei_last = early_node_map[i].end_pfn;
3838                ei_last <<= PAGE_SHIFT;
3839                ei_start = early_node_map[i].start_pfn;
3840                ei_start <<= PAGE_SHIFT;
3841
3842                final_start = max(ei_start, goal);
3843                final_end = min(ei_last, limit);
3844
3845                if (final_start >= final_end)
3846                        continue;
3847
3848                addr = memblock_find_in_range(final_start, final_end, size, align);
3849
3850                if (addr == MEMBLOCK_ERROR)
3851                        continue;
3852
3853                return addr;
3854        }
3855
3856        return MEMBLOCK_ERROR;
3857}
3858#endif
3859
3860int __init add_from_early_node_map(struct range *range, int az,
3861                                   int nr_range, int nid)
3862{
3863        int i;
3864        u64 start, end;
3865
3866        /* need to go over early_node_map to find out good range for node */
3867        for_each_active_range_index_in_nid(i, nid) {
3868                start = early_node_map[i].start_pfn;
3869                end = early_node_map[i].end_pfn;
3870                nr_range = add_range(range, az, nr_range, start, end);
3871        }
3872        return nr_range;
3873}
3874
3875void __init work_with_active_regions(int nid, work_fn_t work_fn, void *data)
3876{
3877        int i;
3878        int ret;
3879
3880        for_each_active_range_index_in_nid(i, nid) {
3881                ret = work_fn(early_node_map[i].start_pfn,
3882                              early_node_map[i].end_pfn, data);
3883                if (ret)
3884                        break;
3885        }
3886}
3887/**
3888 * sparse_memory_present_with_active_regions - Call memory_present for each active range
3889 * @nid: The node to call memory_present for. If MAX_NUMNODES, all nodes will be used.
3890 *
3891 * If an architecture guarantees that all ranges registered with
3892 * add_active_ranges() contain no holes and may be freed, this
3893 * function may be used instead of calling memory_present() manually.
3894 */
3895void __init sparse_memory_present_with_active_regions(int nid)
3896{
3897        int i;
3898
3899        for_each_active_range_index_in_nid(i, nid)
3900                memory_present(early_node_map[i].nid,
3901                                early_node_map[i].start_pfn,
3902                                early_node_map[i].end_pfn);
3903}
3904
3905/**
3906 * get_pfn_range_for_nid - Return the start and end page frames for a node
3907 * @nid: The nid to return the range for. If MAX_NUMNODES, the min and max PFN are returned.
3908 * @start_pfn: Passed by reference. On return, it will have the node start_pfn.
3909 * @end_pfn: Passed by reference. On return, it will have the node end_pfn.
3910 *
3911 * It returns the start and end page frame of a node based on information
3912 * provided by an arch calling add_active_range(). If called for a node
3913 * with no available memory, a warning is printed and the start and end
3914 * PFNs will be 0.
3915 */
3916void __meminit get_pfn_range_for_nid(unsigned int nid,
3917                        unsigned long *start_pfn, unsigned long *end_pfn)
3918{
3919        int i;
3920        *start_pfn = -1UL;
3921        *end_pfn = 0;
3922
3923        for_each_active_range_index_in_nid(i, nid) {
3924                *start_pfn = min(*start_pfn, early_node_map[i].start_pfn);
3925                *end_pfn = max(*end_pfn, early_node_map[i].end_pfn);
3926        }
3927
3928        if (*start_pfn == -1UL)
3929                *start_pfn = 0;
3930}
3931
3932/*
3933 * This finds a zone that can be used for ZONE_MOVABLE pages. The
3934 * assumption is made that zones within a node are ordered in monotonic
3935 * increasing memory addresses so that the "highest" populated zone is used
3936 */
3937static void __init find_usable_zone_for_movable(void)
3938{
3939        int zone_index;
3940        for (zone_index = MAX_NR_ZONES - 1; zone_index >= 0; zone_index--) {
3941                if (zone_index == ZONE_MOVABLE)
3942                        continue;
3943
3944                if (arch_zone_highest_possible_pfn[zone_index] >
3945                                arch_zone_lowest_possible_pfn[zone_index])
3946                        break;
3947        }
3948
3949        VM_BUG_ON(zone_index == -1);
3950        movable_zone = zone_index;
3951}
3952
3953/*
3954 * The zone ranges provided by the architecture do not include ZONE_MOVABLE
3955 * because it is sized independent of architecture. Unlike the other zones,
3956 * the starting point for ZONE_MOVABLE is not fixed. It may be different
3957 * in each node depending on the size of each node and how evenly kernelcore
3958 * is distributed. This helper function adjusts the zone ranges
3959 * provided by the architecture for a given node by using the end of the
3960 * highest usable zone for ZONE_MOVABLE. This preserves the assumption that
3961 * zones within a node are in order of monotonic increases memory addresses
3962 */
3963static void __meminit adjust_zone_range_for_zone_movable(int nid,
3964                                        unsigned long zone_type,
3965                                        unsigned long node_start_pfn,
3966                                        unsigned long node_end_pfn,
3967                                        unsigned long *zone_start_pfn,
3968                                        unsigned long *zone_end_pfn)
3969{
3970        /* Only adjust if ZONE_MOVABLE is on this node */
3971        if (zone_movable_pfn[nid]) {
3972                /* Size ZONE_MOVABLE */
3973                if (zone_type == ZONE_MOVABLE) {
3974                        *zone_start_pfn = zone_movable_pfn[nid];
3975                        *zone_end_pfn = min(node_end_pfn,
3976                                arch_zone_highest_possible_pfn[movable_zone]);
3977
3978                /* Adjust for ZONE_MOVABLE starting within this range */
3979                } else if (*zone_start_pfn < zone_movable_pfn[nid] &&
3980                                *zone_end_pfn > zone_movable_pfn[nid]) {
3981                        *zone_end_pfn = zone_movable_pfn[nid];
3982
3983                /* Check if this whole range is within ZONE_MOVABLE */
3984                } else if (*zone_start_pfn >= zone_movable_pfn[nid])
3985                        *zone_start_pfn = *zone_end_pfn;
3986        }
3987}
3988
3989/*
3990 * Return the number of pages a zone spans in a node, including holes
3991 * present_pages = zone_spanned_pages_in_node() - zone_absent_pages_in_node()
3992 */
3993static unsigned long __meminit zone_spanned_pages_in_node(int nid,
3994                                        unsigned long zone_type,
3995                                        unsigned long *ignored)
3996{
3997        unsigned long node_start_pfn, node_end_pfn;
3998        unsigned long zone_start_pfn, zone_end_pfn;
3999
4000        /* Get the start and end of the node and zone */
4001        get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
4002        zone_start_pfn = arch_zone_lowest_possible_pfn[zone_type];
4003        zone_end_pfn = arch_zone_highest_possible_pfn[zone_type];
4004        adjust_zone_range_for_zone_movable(nid, zone_type,
4005                                node_start_pfn, node_end_pfn,
4006                                &zone_start_pfn, &zone_end_pfn);
4007
4008        /* Check that this node has pages within the zone's required range */
4009        if (zone_end_pfn < node_start_pfn || zone_start_pfn > node_end_pfn)
4010                return 0;
4011
4012        /* Move the zone boundaries inside the node if necessary */
4013        zone_end_pfn = min(zone_end_pfn, node_end_pfn);
4014        zone_start_pfn = max(zone_start_pfn, node_start_pfn);
4015
4016        /* Return the spanned pages */
4017        return zone_end_pfn - zone_start_pfn;
4018}
4019
4020/*
4021 * Return the number of holes in a range on a node. If nid is MAX_NUMNODES,
4022 * then all holes in the requested range will be accounted for.
4023 */
4024unsigned long __meminit __absent_pages_in_range(int nid,
4025                                unsigned long range_start_pfn,
4026                                unsigned long range_end_pfn)
4027{
4028        int i = 0;
4029        unsigned long prev_end_pfn = 0, hole_pages = 0;
4030        unsigned long start_pfn;
4031
4032        /* Find the end_pfn of the first active range of pfns in the node */
4033        i = first_active_region_index_in_nid(nid);
4034        if (i == -1)
4035                return 0;
4036
4037        prev_end_pfn = min(early_node_map[i].start_pfn, range_end_pfn);
4038
4039        /* Account for ranges before physical memory on this node */
4040        if (early_node_map[i].start_pfn > range_start_pfn)
4041                hole_pages = prev_end_pfn - range_start_pfn;
4042
4043        /* Find all holes for the zone within the node */
4044        for (; i != -1; i = next_active_region_index_in_nid(i, nid)) {
4045
4046                /* No need to continue if prev_end_pfn is outside the zone */
4047                if (prev_end_pfn >= range_end_pfn)
4048                        break;
4049
4050                /* Make sure the end of the zone is not within the hole */
4051                start_pfn = min(early_node_map[i].start_pfn, range_end_pfn);
4052                prev_end_pfn = max(prev_end_pfn, range_start_pfn);
4053
4054                /* Update the hole size cound and move on */
4055                if (start_pfn > range_start_pfn) {
4056                        BUG_ON(prev_end_pfn > start_pfn);
4057                        hole_pages += start_pfn - prev_end_pfn;
4058                }
4059                prev_end_pfn = early_node_map[i].end_pfn;
4060        }
4061
4062        /* Account for ranges past physical memory on this node */
4063        if (range_end_pfn > prev_end_pfn)
4064                hole_pages += range_end_pfn -
4065                                max(range_start_pfn, prev_end_pfn);
4066
4067        return hole_pages;
4068}
4069
4070/**
4071 * absent_pages_in_range - Return number of page frames in holes within a range
4072 * @start_pfn: The start PFN to start searching for holes
4073 * @end_pfn: The end PFN to stop searching for holes
4074 *
4075 * It returns the number of pages frames in memory holes within a range.
4076 */
4077unsigned long __init absent_pages_in_range(unsigned long start_pfn,
4078                                                        unsigned long end_pfn)
4079{
4080        return __absent_pages_in_range(MAX_NUMNODES, start_pfn, end_pfn);
4081}
4082
4083/* Return the number of page frames in holes in a zone on a node */
4084static unsigned long __meminit zone_absent_pages_in_node(int nid,
4085                                        unsigned long zone_type,
4086                                        unsigned long *ignored)
4087{
4088        unsigned long node_start_pfn, node_end_pfn;
4089        unsigned long zone_start_pfn, zone_end_pfn;
4090
4091        get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
4092        zone_start_pfn = max(arch_zone_lowest_possible_pfn[zone_type],
4093                                                        node_start_pfn);
4094        zone_end_pfn = min(arch_zone_highest_possible_pfn[zone_type],
4095                                                        node_end_pfn);
4096
4097        adjust_zone_range_for_zone_movable(nid, zone_type,
4098                        node_start_pfn, node_end_pfn,
4099                        &zone_start_pfn, &zone_end_pfn);
4100        return __absent_pages_in_range(nid, zone_start_pfn, zone_end_pfn);
4101}
4102
4103#else
4104static inline unsigned long __meminit zone_spanned_pages_in_node(int nid,
4105                                        unsigned long zone_type,
4106                                        unsigned long *zones_size)
4107{
4108        return zones_size[zone_type];
4109}
4110
4111static inline unsigned long __meminit zone_absent_pages_in_node(int nid,
4112                                                unsigned long zone_type,
4113                                                unsigned long *zholes_size)
4114{
4115        if (!zholes_size)
4116                return 0;
4117
4118        return zholes_size[zone_type];
4119}
4120
4121#endif
4122
4123static void __meminit calculate_node_totalpages(struct pglist_data *pgdat,
4124                unsigned long *zones_size, unsigned long *zholes_size)
4125{
4126        unsigned long realtotalpages, totalpages = 0;
4127        enum zone_type i;
4128
4129        for (i = 0; i < MAX_NR_ZONES; i++)
4130                totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,
4131                                                                zones_size);
4132        pgdat->node_spanned_pages = totalpages;
4133
4134        realtotalpages = totalpages;
4135        for (i = 0; i < MAX_NR_ZONES; i++)
4136                realtotalpages -=
4137                        zone_absent_pages_in_node(pgdat->node_id, i,
4138                                                                zholes_size);
4139        pgdat->node_present_pages = realtotalpages;
4140        printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,
4141                                                        realtotalpages);
4142}
4143
4144#ifndef CONFIG_SPARSEMEM
4145/*
4146 * Calculate the size of the zone->blockflags rounded to an unsigned long
4147 * Start by making sure zonesize is a multiple of pageblock_order by rounding
4148 * up. Then use 1 NR_PAGEBLOCK_BITS worth of bits per pageblock, finally
4149 * round what is now in bits to nearest long in bits, then return it in
4150 * bytes.
4151 */
4152static unsigned long __init usemap_size(unsigned long zonesize)
4153{
4154        unsigned long usemapsize;
4155
4156        usemapsize = roundup(zonesize, pageblock_nr_pages);
4157        usemapsize = usemapsize >> pageblock_order;
4158        usemapsize *= NR_PAGEBLOCK_BITS;
4159        usemapsize = roundup(usemapsize, 8 * sizeof(unsigned long));
4160
4161        return usemapsize / 8;
4162}
4163
4164static void __init setup_usemap(struct pglist_data *pgdat,
4165                                struct zone *zone, unsigned long zonesize)
4166{
4167        unsigned long usemapsize = usemap_size(zonesize);
4168        zone->pageblock_flags = NULL;
4169        if (usemapsize)
4170                zone->pageblock_flags = alloc_bootmem_node_nopanic(pgdat,
4171                                                                   usemapsize);
4172}
4173#else
4174static inline void setup_usemap(struct pglist_data *pgdat,
4175                                struct zone *zone, unsigned long zonesize) {}
4176#endif /* CONFIG_SPARSEMEM */
4177
4178#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
4179
4180/* Return a sensible default order for the pageblock size. */
4181static inline int pageblock_default_order(void)
4182{
4183        if (HPAGE_SHIFT > PAGE_SHIFT)
4184                return HUGETLB_PAGE_ORDER;
4185
4186        return MAX_ORDER-1;
4187}
4188
4189/* Initialise the number of pages represented by NR_PAGEBLOCK_BITS */
4190static inline void __init set_pageblock_order(unsigned int order)
4191{
4192        /* Check that pageblock_nr_pages has not already been setup */
4193        if (pageblock_order)
4194                return;
4195
4196        /*
4197         * Assume the largest contiguous order of interest is a huge page.
4198         * This value may be variable depending on boot parameters on IA64
4199         */
4200        pageblock_order = order;
4201}
4202#else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
4203
4204/*
4205 * When CONFIG_HUGETLB_PAGE_SIZE_VARIABLE is not set, set_pageblock_order()
4206 * and pageblock_default_order() are unused as pageblock_order is set
4207 * at compile-time. See include/linux/pageblock-flags.h for the values of
4208 * pageblock_order based on the kernel config
4209 */
4210static inline int pageblock_default_order(unsigned int order)
4211{
4212        return MAX_ORDER-1;
4213}
4214#define set_pageblock_order(x)  do {} while (0)
4215
4216#endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
4217
4218/*
4219 * Set up the zone data structures:
4220 *   - mark all pages reserved
4221 *   - mark all memory queues empty
4222 *   - clear the memory bitmaps
4223 */
4224static void __paginginit free_area_init_core(struct pglist_data *pgdat,
4225                unsigned long *zones_size, unsigned long *zholes_size)
4226{
4227        enum zone_type j;
4228        int nid = pgdat->node_id;
4229        unsigned long zone_start_pfn = pgdat->node_start_pfn;
4230        int ret;
4231
4232        pgdat_resize_init(pgdat);
4233        pgdat->nr_zones = 0;
4234        init_waitqueue_head(&pgdat->kswapd_wait);
4235        pgdat->kswapd_max_order = 0;
4236        pgdat_page_cgroup_init(pgdat);
4237        
4238        for (j = 0; j < MAX_NR_ZONES; j++) {
4239                struct zone *zone = pgdat->node_zones + j;
4240                unsigned long size, realsize, memmap_pages;
4241                enum lru_list l;
4242
4243                size = zone_spanned_pages_in_node(nid, j, zones_size);
4244                realsize = size - zone_absent_pages_in_node(nid, j,
4245                                                                zholes_size);
4246
4247                /*
4248                 * Adjust realsize so that it accounts for how much memory
4249                 * is used by this zone for memmap. This affects the watermark
4250                 * and per-cpu initialisations
4251                 */
4252                memmap_pages =
4253                        PAGE_ALIGN(size * sizeof(struct page)) >> PAGE_SHIFT;
4254                if (realsize >= memmap_pages) {
4255                        realsize -= memmap_pages;
4256                        if (memmap_pages)
4257                                printk(KERN_DEBUG
4258                                       "  %s zone: %lu pages used for memmap\n",
4259                                       zone_names[j], memmap_pages);
4260                } else
4261                        printk(KERN_WARNING
4262                                "  %s zone: %lu pages exceeds realsize %lu\n",
4263                                zone_names[j], memmap_pages, realsize);
4264
4265                /* Account for reserved pages */
4266                if (j == 0 && realsize > dma_reserve) {
4267                        realsize -= dma_reserve;
4268                        printk(KERN_DEBUG "  %s zone: %lu pages reserved\n",
4269                                        zone_names[0], dma_reserve);
4270                }
4271
4272                if (!is_highmem_idx(j))
4273                        nr_kernel_pages += realsize;
4274                nr_all_pages += realsize;
4275
4276                zone->spanned_pages = size;
4277                zone->present_pages = realsize;
4278#ifdef CONFIG_NUMA
4279                zone->node = nid;
4280                zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)
4281                                                / 100;
4282                zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;
4283#endif
4284                zone->name = zone_names[j];
4285                spin_lock_init(&zone->lock);
4286                spin_lock_init(&zone->lru_lock);
4287                zone_seqlock_init(zone);
4288                zone->zone_pgdat = pgdat;
4289
4290                zone_pcp_init(zone);
4291                for_each_lru(l) {
4292                        INIT_LIST_HEAD(&zone->lru[l].list);
4293                        zone->reclaim_stat.nr_saved_scan[l] = 0;
4294                }
4295                zone->reclaim_stat.recent_rotated[0] = 0;
4296                zone->reclaim_stat.recent_rotated[1] = 0;
4297                zone->reclaim_stat.recent_scanned[0] = 0;
4298                zone->reclaim_stat.recent_scanned[1] = 0;
4299                zap_zone_vm_stats(zone);
4300                zone->flags = 0;
4301                if (!size)
4302                        continue;
4303
4304                set_pageblock_order(pageblock_default_order());
4305                setup_usemap(pgdat, zone, size);
4306                ret = init_currently_empty_zone(zone, zone_start_pfn,
4307                                                size, MEMMAP_EARLY);
4308                BUG_ON(ret);
4309                memmap_init(size, nid, j, zone_start_pfn);
4310                zone_start_pfn += size;
4311        }
4312}
4313
4314static void __init_refok alloc_node_mem_map(struct pglist_data *pgdat)
4315{
4316        /* Skip empty nodes */
4317        if (!pgdat->node_spanned_pages)
4318                return;
4319
4320#ifdef CONFIG_FLAT_NODE_MEM_MAP
4321        /* ia64 gets its own node_mem_map, before this, without bootmem */
4322        if (!pgdat->node_mem_map) {
4323                unsigned long size, start, end;
4324                struct page *map;
4325
4326                /*
4327                 * The zone's endpoints aren't required to be MAX_ORDER
4328                 * aligned but the node_mem_map endpoints must be in order
4329                 * for the buddy allocator to function correctly.
4330                 */
4331                start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);
4332                end = pgdat->node_start_pfn + pgdat->node_spanned_pages;
4333                end = ALIGN(end, MAX_ORDER_NR_PAGES);
4334                size =  (end - start) * sizeof(struct page);
4335                map = alloc_remap(pgdat->node_id, size);
4336                if (!map)
4337                        map = alloc_bootmem_node_nopanic(pgdat, size);
4338                pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);
4339        }
4340#ifndef CONFIG_NEED_MULTIPLE_NODES
4341        /*
4342         * With no DISCONTIG, the global mem_map is just set as node 0's
4343         */
4344        if (pgdat == NODE_DATA(0)) {
4345                mem_map = NODE_DATA(0)->node_mem_map;
4346#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
4347                if (page_to_pfn(mem_map) != pgdat->node_start_pfn)
4348                        mem_map -= (pgdat->node_start_pfn - ARCH_PFN_OFFSET);
4349#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
4350        }
4351#endif
4352#endif /* CONFIG_FLAT_NODE_MEM_MAP */
4353}
4354
4355void __paginginit free_area_init_node(int nid, unsigned long *zones_size,
4356                unsigned long node_start_pfn, unsigned long *zholes_size)
4357{
4358        pg_data_t *pgdat = NODE_DATA(nid);
4359
4360        pgdat->node_id = nid;
4361        pgdat->node_start_pfn = node_start_pfn;
4362        calculate_node_totalpages(pgdat, zones_size, zholes_size);
4363
4364        alloc_node_mem_map(pgdat);
4365#ifdef CONFIG_FLAT_NODE_MEM_MAP
4366        printk(KERN_DEBUG "free_area_init_node: node %d, pgdat %08lx, node_mem_map %08lx\n",
4367                nid, (unsigned long)pgdat,
4368                (unsigned long)pgdat->node_mem_map);
4369#endif
4370
4371        free_area_init_core(pgdat, zones_size, zholes_size);
4372}
4373
4374#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
4375
4376#if MAX_NUMNODES > 1
4377/*
4378 * Figure out the number of possible node ids.
4379 */
4380static void __init setup_nr_node_ids(void)
4381{
4382        unsigned int node;
4383        unsigned int highest = 0;
4384
4385        for_each_node_mask(node, node_possible_map)
4386                highest = node;
4387        nr_node_ids = highest + 1;
4388}
4389#else
4390static inline void setup_nr_node_ids(void)
4391{
4392}
4393#endif
4394
4395/**
4396 * add_active_range - Register a range of PFNs backed by physical memory
4397 * @nid: The node ID the range resides on
4398 * @start_pfn: The start PFN of the available physical memory
4399 * @end_pfn: The end PFN of the available physical memory
4400 *
4401 * These ranges are stored in an early_node_map[] and later used by
4402 * free_area_init_nodes() to calculate zone sizes and holes. If the
4403 * range spans a memory hole, it is up to the architecture to ensure
4404 * the memory is not freed by the bootmem allocator. If possible
4405 * the range being registered will be merged with existing ranges.
4406 */
4407void __init add_active_range(unsigned int nid, unsigned long start_pfn,
4408                                                unsigned long end_pfn)
4409{
4410        int i;
4411
4412        mminit_dprintk(MMINIT_TRACE, "memory_register",
4413                        "Entering add_active_range(%d, %#lx, %#lx) "
4414                        "%d entries of %d used\n",
4415                        nid, start_pfn, end_pfn,
4416                        nr_nodemap_entries, MAX_ACTIVE_REGIONS);
4417
4418        mminit_validate_memmodel_limits(&start_pfn, &end_pfn);
4419
4420        /* Merge with existing active regions if possible */
4421        for (i = 0; i < nr_nodemap_entries; i++) {
4422                if (early_node_map[i].nid != nid)
4423                        continue;
4424
4425                /* Skip if an existing region covers this new one */
4426                if (start_pfn >= early_node_map[i].start_pfn &&
4427                                end_pfn <= early_node_map[i].end_pfn)
4428                        return;
4429
4430                /* Merge forward if suitable */
4431                if (start_pfn <= early_node_map[i].end_pfn &&
4432                                end_pfn > early_node_map[i].end_pfn) {
4433                        early_node_map[i].end_pfn = end_pfn;
4434                        return;
4435                }
4436
4437                /* Merge backward if suitable */
4438                if (start_pfn < early_node_map[i].start_pfn &&
4439                                end_pfn >= early_node_map[i].start_pfn) {
4440                        early_node_map[i].start_pfn = start_pfn;
4441                        return;
4442                }
4443        }
4444
4445        /* Check that early_node_map is large enough */
4446        if (i >= MAX_ACTIVE_REGIONS) {
4447                printk(KERN_CRIT "More than %d memory regions, truncating\n",
4448                                                        MAX_ACTIVE_REGIONS);
4449                return;
4450        }
4451
4452        early_node_map[i].nid = nid;
4453        early_node_map[i].start_pfn = start_pfn;
4454        early_node_map[i].end_pfn = end_pfn;
4455        nr_nodemap_entries = i + 1;
4456}
4457
4458/**
4459 * remove_active_range - Shrink an existing registered range of PFNs
4460 * @nid: The node id the range is on that should be shrunk
4461 * @start_pfn: The new PFN of the range
4462 * @end_pfn: The new PFN of the range
4463 *
4464 * i386 with NUMA use alloc_remap() to store a node_mem_map on a local node.
4465 * The map is kept near the end physical page range that has already been
4466 * registered. This function allows an arch to shrink an existing registered
4467 * range.
4468 */
4469void __init remove_active_range(unsigned int nid, unsigned long start_pfn,
4470                                unsigned long end_pfn)
4471{
4472        int i, j;
4473        int removed = 0;
4474
4475        printk(KERN_DEBUG "remove_active_range (%d, %lu, %lu)\n",
4476                          nid, start_pfn, end_pfn);
4477
4478        /* Find the old active region end and shrink */
4479        for_each_active_range_index_in_nid(i, nid) {
4480                if (early_node_map[i].start_pfn >= start_pfn &&
4481                    early_node_map[i].end_pfn <= end_pfn) {
4482                        /* clear it */
4483                        early_node_map[i].start_pfn = 0;
4484                        early_node_map[i].end_pfn = 0;
4485                        removed = 1;
4486                        continue;
4487                }
4488                if (early_node_map[i].start_pfn < start_pfn &&
4489                    early_node_map[i].end_pfn > start_pfn) {
4490                        unsigned long temp_end_pfn = early_node_map[i].end_pfn;
4491                        early_node_map[i].end_pfn = start_pfn;
4492                        if (temp_end_pfn > end_pfn)
4493                                add_active_range(nid, end_pfn, temp_end_pfn);
4494                        continue;
4495                }
4496                if (early_node_map[i].start_pfn >= start_pfn &&
4497                    early_node_map[i].end_pfn > end_pfn &&
4498                    early_node_map[i].start_pfn < end_pfn) {
4499                        early_node_map[i].start_pfn = end_pfn;
4500                        continue;
4501                }
4502        }
4503
4504        if (!removed)
4505                return;
4506
4507        /* remove the blank ones */
4508        for (i = nr_nodemap_entries - 1; i > 0; i--) {
4509                if (early_node_map[i].nid != nid)
4510                        continue;
4511                if (early_node_map[i].end_pfn)
4512                        continue;
4513                /* we found it, get rid of it */
4514                for (j = i; j < nr_nodemap_entries - 1; j++)
4515                        memcpy(&early_node_map[j], &early_node_map[j+1],
4516                                sizeof(early_node_map[j]));
4517                j = nr_nodemap_entries - 1;
4518                memset(&early_node_map[j], 0, sizeof(early_node_map[j]));
4519                nr_nodemap_entries--;
4520        }
4521}
4522
4523/**
4524 * remove_all_active_ranges - Remove all currently registered regions
4525 *
4526 * During discovery, it may be found that a table like SRAT is invalid
4527 * and an alternative discovery method must be used. This function removes
4528 * all currently registered regions.
4529 */
4530void __init remove_all_active_ranges(void)
4531{
4532        memset(early_node_map, 0, sizeof(early_node_map));
4533        nr_nodemap_entries = 0;
4534}
4535
4536/* Compare two active node_active_regions */
4537static int __init cmp_node_active_region(const void *a, const void *b)
4538{
4539        struct node_active_region *arange = (struct node_active_region *)a;
4540        struct node_active_region *brange = (struct node_active_region *)b;
4541
4542        /* Done this way to avoid overflows */
4543        if (arange->start_pfn > brange->start_pfn)
4544                return 1;
4545        if (arange->start_pfn < brange->start_pfn)
4546                return -1;
4547
4548        return 0;
4549}
4550
4551/* sort the node_map by start_pfn */
4552void __init sort_node_map(void)
4553{
4554        sort(early_node_map, (size_t)nr_nodemap_entries,
4555                        sizeof(struct node_active_region),
4556                        cmp_node_active_region, NULL);
4557}
4558
4559/* Find the lowest pfn for a node */
4560static unsigned long __init find_min_pfn_for_node(int nid)
4561{
4562        int i;
4563        unsigned long min_pfn = ULONG_MAX;
4564
4565        /* Assuming a sorted map, the first range found has the starting pfn */
4566        for_each_active_range_index_in_nid(i, nid)
4567                min_pfn = min(min_pfn, early_node_map[i].start_pfn);
4568
4569        if (min_pfn == ULONG_MAX) {
4570                printk(KERN_WARNING
4571                        "Could not find start_pfn for node %d\n", nid);
4572                return 0;
4573        }
4574
4575        return min_pfn;
4576}
4577
4578/**
4579 * find_min_pfn_with_active_regions - Find the minimum PFN registered
4580 *
4581 * It returns the minimum PFN based on information provided via
4582 * add_active_range().
4583 */
4584unsigned long __init find_min_pfn_with_active_regions(void)
4585{
4586        return find_min_pfn_for_node(MAX_NUMNODES);
4587}
4588
4589/*
4590 * early_calculate_totalpages()
4591 * Sum pages in active regions for movable zone.
4592 * Populate N_HIGH_MEMORY for calculating usable_nodes.
4593 */
4594static unsigned long __init early_calculate_totalpages(void)
4595{
4596        int i;
4597        unsigned long totalpages = 0;
4598
4599        for (i = 0; i < nr_nodemap_entries; i++) {
4600                unsigned long pages = early_node_map[i].end_pfn -
4601                                                early_node_map[i].start_pfn;
4602                totalpages += pages;
4603                if (pages)
4604                        node_set_state(early_node_map[i].nid, N_HIGH_MEMORY);
4605        }
4606        return totalpages;
4607}
4608
4609/*
4610 * Find the PFN the Movable zone begins in each node. Kernel memory
4611 * is spread evenly between nodes as long as the nodes have enough
4612 * memory. When they don't, some nodes will have more kernelcore than
4613 * others
4614 */
4615static void __init find_zone_movable_pfns_for_nodes(unsigned long *movable_pfn)
4616{
4617        int i, nid;
4618        unsigned long usable_startpfn;
4619        unsigned long kernelcore_node, kernelcore_remaining;
4620        /* save the state before borrow the nodemask */
4621        nodemask_t saved_node_state = node_states[N_HIGH_MEMORY];
4622        unsigned long totalpages = early_calculate_totalpages();
4623        int usable_nodes = nodes_weight(node_states[N_HIGH_MEMORY]);
4624
4625        /*
4626         * If movablecore was specified, calculate what size of
4627         * kernelcore that corresponds so that memory usable for
4628         * any allocation type is evenly spread. If both kernelcore
4629         * and movablecore are specified, then the value of kernelcore
4630         * will be used for required_kernelcore if it's greater than
4631         * what movablecore would have allowed.
4632         */
4633        if (required_movablecore) {
4634                unsigned long corepages;
4635
4636                /*
4637                 * Round-up so that ZONE_MOVABLE is at least as large as what
4638                 * was requested by the user
4639                 */
4640                required_movablecore =
4641                        roundup(required_movablecore, MAX_ORDER_NR_PAGES);
4642                corepages = totalpages - required_movablecore;
4643
4644                required_kernelcore = max(required_kernelcore, corepages);
4645        }
4646
4647        /* If kernelcore was not specified, there is no ZONE_MOVABLE */
4648        if (!required_kernelcore)
4649                goto out;
4650
4651        /* usable_startpfn is the lowest possible pfn ZONE_MOVABLE can be at */
4652        find_usable_zone_for_movable();
4653        usable_startpfn = arch_zone_lowest_possible_pfn[movable_zone];
4654
4655restart:
4656        /* Spread kernelcore memory as evenly as possible throughout nodes */
4657        kernelcore_node = required_kernelcore / usable_nodes;
4658        for_each_node_state(nid, N_HIGH_MEMORY) {
4659                /*
4660                 * Recalculate kernelcore_node if the division per node
4661                 * now exceeds what is necessary to satisfy the requested
4662                 * amount of memory for the kernel
4663                 */
4664                if (required_kernelcore < kernelcore_node)
4665                        kernelcore_node = required_kernelcore / usable_nodes;
4666
4667                /*
4668                 * As the map is walked, we track how much memory is usable
4669                 * by the kernel using kernelcore_remaining. When it is
4670                 * 0, the rest of the node is usable by ZONE_MOVABLE
4671                 */
4672                kernelcore_remaining = kernelcore_node;
4673
4674                /* Go through each range of PFNs within this node */
4675                for_each_active_range_index_in_nid(i, nid) {
4676                        unsigned long start_pfn, end_pfn;
4677                        unsigned long size_pages;
4678
4679                        start_pfn = max(early_node_map[i].start_pfn,
4680                                                zone_movable_pfn[nid]);
4681                        end_pfn = early_node_map[i].end_pfn;
4682                        if (start_pfn >= end_pfn)
4683                                continue;
4684
4685                        /* Account for what is only usable for kernelcore */
4686                        if (start_pfn < usable_startpfn) {
4687                                unsigned long kernel_pages;
4688                                kernel_pages = min(end_pfn, usable_startpfn)
4689                                                                - start_pfn;
4690
4691                                kernelcore_remaining -= min(kernel_pages,
4692                                                        kernelcore_remaining);
4693                                required_kernelcore -= min(kernel_pages,
4694                                                        required_kernelcore);
4695
4696                                /* Continue if range is now fully accounted */
4697                                if (end_pfn <= usable_startpfn) {
4698
4699                                        /*
4700                                         * Push zone_movable_pfn to the end so
4701                                         * that if we have to rebalance
4702                                         * kernelcore across nodes, we will
4703                                         * not double account here
4704                                         */
4705                                        zone_movable_pfn[nid] = end_pfn;
4706                                        continue;
4707                                }
4708                                start_pfn = usable_startpfn;
4709                        }
4710
4711                        /*
4712                         * The usable PFN range for ZONE_MOVABLE is from
4713                         * start_pfn->end_pfn. Calculate size_pages as the
4714                         * number of pages used as kernelcore
4715                         */
4716                        size_pages = end_pfn - start_pfn;
4717                        if (size_pages > kernelcore_remaining)
4718                                size_pages = kernelcore_remaining;
4719                        zone_movable_pfn[nid] = start_pfn + size_pages;
4720
4721                        /*
4722                         * Some kernelcore has been met, update counts and
4723                         * break if the kernelcore for this node has been
4724                         * satisified
4725                         */
4726                        required_kernelcore -= min(required_kernelcore,
4727                                                                size_pages);
4728                        kernelcore_remaining -= size_pages;
4729                        if (!kernelcore_remaining)
4730                                break;
4731                }
4732        }
4733
4734        /*
4735         * If there is still required_kernelcore, we do another pass with one
4736         * less node in the count. This will push zone_movable_pfn[nid] further
4737         * along on the nodes that still have memory until kernelcore is
4738         * satisified
4739         */
4740        usable_nodes--;
4741        if (usable_nodes && required_kernelcore > usable_nodes)
4742                goto restart;
4743
4744        /* Align start of ZONE_MOVABLE on all nids to MAX_ORDER_NR_PAGES */
4745        for (nid = 0; nid < MAX_NUMNODES; nid++)
4746                zone_movable_pfn[nid] =
4747                        roundup(zone_movable_pfn[nid], MAX_ORDER_NR_PAGES);
4748
4749out:
4750        /* restore the node_state */
4751        node_states[N_HIGH_MEMORY] = saved_node_state;
4752}
4753
4754/* Any regular memory on that node ? */
4755static void check_for_regular_memory(pg_data_t *pgdat)
4756{
4757#ifdef CONFIG_HIGHMEM
4758        enum zone_type zone_type;
4759
4760        for (zone_type = 0; zone_type <= ZONE_NORMAL; zone_type++) {
4761                struct zone *zone = &pgdat->node_zones[zone_type];
4762                if (zone->present_pages)
4763                        node_set_state(zone_to_nid(zone), N_NORMAL_MEMORY);
4764        }
4765#endif
4766}
4767
4768/**
4769 * free_area_init_nodes - Initialise all pg_data_t and zone data
4770 * @max_zone_pfn: an array of max PFNs for each zone
4771 *
4772 * This will call free_area_init_node() for each active node in the system.
4773 * Using the page ranges provided by add_active_range(), the size of each
4774 * zone in each node and their holes is calculated. If the maximum PFN
4775 * between two adjacent zones match, it is assumed that the zone is empty.
4776 * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed
4777 * that arch_max_dma32_pfn has no pages. It is also assumed that a zone
4778 * starts where the previous one ended. For example, ZONE_DMA32 starts
4779 * at arch_max_dma_pfn.
4780 */
4781void __init free_area_init_nodes(unsigned long *max_zone_pfn)
4782{
4783        unsigned long nid;
4784        int i;
4785
4786        /* Sort early_node_map as initialisation assumes it is sorted */
4787        sort_node_map();
4788
4789        /* Record where the zone boundaries are */
4790        memset(arch_zone_lowest_possible_pfn, 0,
4791                                sizeof(arch_zone_lowest_possible_pfn));
4792        memset(arch_zone_highest_possible_pfn, 0,
4793                                sizeof(arch_zone_highest_possible_pfn));
4794        arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();
4795        arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];
4796        for (i = 1; i < MAX_NR_ZONES; i++) {
4797                if (i == ZONE_MOVABLE)
4798                        continue;
4799                arch_zone_lowest_possible_pfn[i] =
4800                        arch_zone_highest_possible_pfn[i-1];
4801                arch_zone_highest_possible_pfn[i] =
4802                        max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);
4803        }
4804        arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;
4805        arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;
4806
4807        /* Find the PFNs that ZONE_MOVABLE begins at in each node */
4808        memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));
4809        find_zone_movable_pfns_for_nodes(zone_movable_pfn);
4810
4811        /* Print out the zone ranges */
4812        printk("Zone PFN ranges:\n");
4813        for (i = 0; i < MAX_NR_ZONES; i++) {
4814                if (i == ZONE_MOVABLE)
4815                        continue;
4816                printk("  %-8s ", zone_names[i]);
4817                if (arch_zone_lowest_possible_pfn[i] ==
4818                                arch_zone_highest_possible_pfn[i])
4819                        printk("empty\n");
4820                else
4821                        printk("%0#10lx -> %0#10lx\n",
4822                                arch_zone_lowest_possible_pfn[i],
4823                                arch_zone_highest_possible_pfn[i]);
4824        }
4825
4826        /* Print out the PFNs ZONE_MOVABLE begins at in each node */
4827        printk("Movable zone start PFN for each node\n");
4828        for (i = 0; i < MAX_NUMNODES; i++) {
4829                if (zone_movable_pfn[i])
4830                        printk("  Node %d: %lu\n", i, zone_movable_pfn[i]);
4831        }
4832
4833        /* Print out the early_node_map[] */
4834        printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);
4835        for (i = 0; i < nr_nodemap_entries; i++)
4836                printk("  %3d: %0#10lx -> %0#10lx\n", early_node_map[i].nid,
4837                                                early_node_map[i].start_pfn,
4838                                                early_node_map[i].end_pfn);
4839
4840        /* Initialise every node */
4841        mminit_verify_pageflags_layout();
4842        setup_nr_node_ids();
4843        for_each_online_node(nid) {
4844                pg_data_t *pgdat = NODE_DATA(nid);
4845                free_area_init_node(nid, NULL,
4846                                find_min_pfn_for_node(nid), NULL);
4847
4848                /* Any memory on that node */
4849                if (pgdat->node_present_pages)
4850                        node_set_state(nid, N_HIGH_MEMORY);
4851                check_for_regular_memory(pgdat);
4852        }
4853}
4854
4855static int __init cmdline_parse_core(char *p, unsigned long *core)
4856{
4857        unsigned long long coremem;
4858        if (!p)
4859                return -EINVAL;
4860
4861        coremem = memparse(p, &p);
4862        *core = coremem >> PAGE_SHIFT;
4863
4864        /* Paranoid check that UL is enough for the coremem value */
4865        WARN_ON((coremem >> PAGE_SHIFT) > ULONG_MAX);
4866
4867        return 0;
4868}
4869
4870/*
4871 * kernelcore=size sets the amount of memory for use for allocations that
4872 * cannot be reclaimed or migrated.
4873 */
4874static int __init cmdline_parse_kernelcore(char *p)
4875{
4876        return cmdline_parse_core(p, &required_kernelcore);
4877}
4878
4879/*
4880 * movablecore=size sets the amount of memory for use for allocations that
4881 * can be reclaimed or migrated.
4882 */
4883static int __init cmdline_parse_movablecore(char *p)
4884{
4885        return cmdline_parse_core(p, &required_movablecore);
4886}
4887
4888early_param("kernelcore", cmdline_parse_kernelcore);
4889early_param("movablecore", cmdline_parse_movablecore);
4890
4891#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
4892
4893/**
4894 * set_dma_reserve - set the specified number of pages reserved in the first zone
4895 * @new_dma_reserve: The number of pages to mark reserved
4896 *
4897 * The per-cpu batchsize and zone watermarks are determined by present_pages.
4898 * In the DMA zone, a significant percentage may be consumed by kernel image
4899 * and other unfreeable allocations which can skew the watermarks badly. This
4900 * function may optionally be used to account for unfreeable pages in the
4901 * first zone (e.g., ZONE_DMA). The effect will be lower watermarks and
4902 * smaller per-cpu batchsize.
4903 */
4904void __init set_dma_reserve(unsigned long new_dma_reserve)
4905{
4906        dma_reserve = new_dma_reserve;
4907}
4908
4909void __init free_area_init(unsigned long *zones_size)
4910{
4911        free_area_init_node(0, zones_size,
4912                        __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
4913}
4914
4915static int page_alloc_cpu_notify(struct notifier_block *self,
4916</