mm/page_alloc.c

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