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/config.h>
  18 #include <linux/stddef.h>
  19 #include <linux/mm.h>
  20 #include <linux/swap.h>
  21 #include <linux/interrupt.h>
  22 #include <linux/pagemap.h>
  23 #include <linux/bootmem.h>
  24 #include <linux/compiler.h>
  25 #include <linux/module.h>
  26 #include <linux/suspend.h>
  27 #include <linux/pagevec.h>
  28 #include <linux/blkdev.h>
  29 #include <linux/slab.h>
  30 #include <linux/notifier.h>
  31 #include <linux/topology.h>
  32 #include <linux/sysctl.h>
  33 #include <linux/cpu.h>
  34 #include <linux/cpuset.h>
  35 #include <linux/nodemask.h>
  36 #include <linux/vmalloc.h>
  37 #include <linux/vs_limit.h>
  38
  39 #include <asm/tlbflush.h>
  40 #include "internal.h"
  41
  42 /*
  43  * MCD - HACK: Find somewhere to initialize this EARLY, or make this
  44  * initializer cleaner
  45  */
  46 nodemask_t node_online_map = { { [0] = 1UL } };
  47 EXPORT_SYMBOL(node_online_map);
  48 nodemask_t node_possible_map = NODE_MASK_ALL;
  49 EXPORT_SYMBOL(node_possible_map);
  50 struct pglist_data *pgdat_list;
  51 unsigned long totalram_pages;
  52 unsigned long totalhigh_pages;
  53 long nr_swap_pages;
  54
  55 /*
  56  * results with 256, 32 in the lowmem_reserve sysctl:
  57  *      1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
  58  *      1G machine -> (16M dma, 784M normal, 224M high)
  59  *      NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
  60  *      HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
  61  *      HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
  62  */
  63 int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { 256, 32 };
  64
  65 EXPORT_SYMBOL(totalram_pages);
  66 EXPORT_SYMBOL(nr_swap_pages);
  67
  68 #ifdef CONFIG_CRASH_DUMP
  69 /* This symbol has to be exported to use 'for_each_pgdat' macro by modules. */
  70 EXPORT_SYMBOL(pgdat_list);
  71 #endif
  72
  73 /*
  74  * Used by page_zone() to look up the address of the struct zone whose
  75  * id is encoded in the upper bits of page->flags
  76  */
  77 struct zone *zone_table[1 << (ZONES_SHIFT + NODES_SHIFT)];
  78 EXPORT_SYMBOL(zone_table);
  79
  80 static char *zone_names[MAX_NR_ZONES] = { "DMA", "Normal", "HighMem" };
  81 int min_free_kbytes = 1024;
  82
  83 unsigned long __initdata nr_kernel_pages;
  84 unsigned long __initdata nr_all_pages;
  85
  86 /*
  87  * Temporary debugging check for pages not lying within a given zone.
  88  */
  89 static int bad_range(struct zone *zone, struct page *page)
  90 {
  91         if (page_to_pfn(page) >= zone->zone_start_pfn + zone->spanned_pages)
  92                 return 1;
  93         if (page_to_pfn(page) < zone->zone_start_pfn)
  94                 return 1;
  95 #ifdef CONFIG_HOLES_IN_ZONE
  96         if (!pfn_valid(page_to_pfn(page)))
  97                 return 1;
  98 #endif
  99         if (zone != page_zone(page))
 100                 return 1;
 101         return 0;
 102 }
 103
 104 static void bad_page(const char *function, struct page *page)
 105 {
 106         printk(KERN_EMERG "Bad page state at %s (in process '%s', page %p)\n",
 107                 function, current->comm, page);
 108         printk(KERN_EMERG "flags:0x%0*lx mapping:%p mapcount:%d count:%d (%s)\n",
 109                 (int)(2*sizeof(page_flags_t)), (unsigned long)page->flags,
 110                 page->mapping, page_mapcount(page), page_count(page), print_tainted());
 111         printk(KERN_EMERG "Backtrace:\n");
 112         dump_stack();
 113         printk(KERN_EMERG "Trying to fix it up, but a reboot is needed\n");
 114         page->flags &= ~(1 << PG_private        |
 115                         1 << PG_locked  |
 116                         1 << PG_lru     |
 117                         1 << PG_active  |
 118                         1 << PG_dirty   |
 119                         1 << PG_swapcache |
 120                         1 << PG_writeback);
 121         set_page_count(page, 0);
 122         reset_page_mapcount(page);
 123         page->mapping = NULL;
 124         tainted |= TAINT_BAD_PAGE;
 125 }
 126
 127 #if !defined(CONFIG_HUGETLB_PAGE) && !defined(CONFIG_CRASH_DUMP)
 128 #define prep_compound_page(page, order) do { } while (0)
 129 #define destroy_compound_page(page, order) do { } while (0)
 130 #else
 131 /*
 132  * Higher-order pages are called "compound pages".  They are structured thusly:
 133  *
 134  * The first PAGE_SIZE page is called the "head page".
 135  *
 136  * The remaining PAGE_SIZE pages are called "tail pages".
 137  *
 138  * All pages have PG_compound set.  All pages have their ->private pointing at
 139  * the head page (even the head page has this).
 140  *
 141  * The first tail page's ->mapping, if non-zero, holds the address of the
 142  * compound page's put_page() function.
 143  *
 144  * The order of the allocation is stored in the first tail page's ->index
 145  * This is only for debug at present.  This usage means that zero-order pages
 146  * may not be compound.
 147  */
 148 static void prep_compound_page(struct page *page, unsigned long order)
 149 {
 150         int i;
 151         int nr_pages = 1 << order;
 152
 153         page[1].mapping = NULL;
 154         page[1].index = order;
 155         for (i = 0; i < nr_pages; i++) {
 156                 struct page *p = page + i;
 157
 158                 SetPageCompound(p);
 159                 p->private = (unsigned long)page;
 160         }
 161 }
 162
 163 static void destroy_compound_page(struct page *page, unsigned long order)
 164 {
 165         int i;
 166         int nr_pages = 1 << order;
 167
 168         if (!PageCompound(page))
 169                 return;
 170
 171         if (page[1].index != order)
 172                 bad_page(__FUNCTION__, page);
 173
 174         for (i = 0; i < nr_pages; i++) {
 175                 struct page *p = page + i;
 176
 177                 if (!PageCompound(p))
 178                         bad_page(__FUNCTION__, page);
 179                 if (p->private != (unsigned long)page)
 180                         bad_page(__FUNCTION__, page);
 181                 ClearPageCompound(p);
 182         }
 183 }
 184 #endif          /* CONFIG_HUGETLB_PAGE */
 185
 186 /*
 187  * function for dealing with page's order in buddy system.
 188  * zone->lock is already acquired when we use these.
 189  * So, we don't need atomic page->flags operations here.
 190  */
 191 static inline unsigned long page_order(struct page *page) {
 192         return page->private;
 193 }
 194
 195 static inline void set_page_order(struct page *page, int order) {
 196         page->private = order;
 197         __SetPagePrivate(page);
 198 }
 199
 200 static inline void rmv_page_order(struct page *page)
 201 {
 202         __ClearPagePrivate(page);
 203         page->private = 0;
 204 }
 205
 206 /*
 207  * Locate the struct page for both the matching buddy in our
 208  * pair (buddy1) and the combined O(n+1) page they form (page).
 209  *
 210  * 1) Any buddy B1 will have an order O twin B2 which satisfies
 211  * the following equation:
 212  *     B2 = B1 ^ (1 << O)
 213  * For example, if the starting buddy (buddy2) is #8 its order
 214  * 1 buddy is #10:
 215  *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
 216  *
 217  * 2) Any buddy B will have an order O+1 parent P which
 218  * satisfies the following equation:
 219  *     P = B & ~(1 << O)
 220  *
 221  * Assumption: *_mem_map is contigious at least up to MAX_ORDER
 222  */
 223 static inline struct page *
 224 __page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
 225 {
 226         unsigned long buddy_idx = page_idx ^ (1 << order);
 227
 228         return page + (buddy_idx - page_idx);
 229 }
 230
 231 static inline unsigned long
 232 __find_combined_index(unsigned long page_idx, unsigned int order)
 233 {
 234         return (page_idx & ~(1 << order));
 235 }
 236
 237 /*
 238  * This function checks whether a page is free && is the buddy
 239  * we can do coalesce a page and its buddy if
 240  * (a) the buddy is free &&
 241  * (b) the buddy is on the buddy system &&
 242  * (c) a page and its buddy have the same order.
 243  * for recording page's order, we use page->private and PG_private.
 244  *
 245  */
 246 static inline int page_is_buddy(struct page *page, int order)
 247 {
 248        if (PagePrivate(page)           &&
 249            (page_order(page) == order) &&
 250            !PageReserved(page)         &&
 251             page_count(page) == 0)
 252                return 1;
 253        return 0;
 254 }
 255
 256 /*
 257  * Freeing function for a buddy system allocator.
 258  *
 259  * The concept of a buddy system is to maintain direct-mapped table
 260  * (containing bit values) for memory blocks of various "orders".
 261  * The bottom level table contains the map for the smallest allocatable
 262  * units of memory (here, pages), and each level above it describes
 263  * pairs of units from the levels below, hence, "buddies".
 264  * At a high level, all that happens here is marking the table entry
 265  * at the bottom level available, and propagating the changes upward
 266  * as necessary, plus some accounting needed to play nicely with other
 267  * parts of the VM system.
 268  * At each level, we keep a list of pages, which are heads of continuous
 269  * free pages of length of (1 << order) and marked with PG_Private.Page's
 270  * order is recorded in page->private field.
 271  * So when we are allocating or freeing one, we can derive the state of the
 272  * other.  That is, if we allocate a small block, and both were
 273  * free, the remainder of the region must be split into blocks.
 274  * If a block is freed, and its buddy is also free, then this
 275  * triggers coalescing into a block of larger size.
 276  *
 277  * -- wli
 278  */
 279
 280 static inline void __free_pages_bulk (struct page *page,
 281                 struct zone *zone, unsigned int order)
 282 {
 283         unsigned long page_idx;
 284         int order_size = 1 << order;
 285
 286         if (unlikely(order))
 287                 destroy_compound_page(page, order);
 288
 289         page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
 290
 291         BUG_ON(page_idx & (order_size - 1));
 292         BUG_ON(bad_range(zone, page));
 293
 294         zone->free_pages += order_size;
 295         while (order < MAX_ORDER-1) {
 296                 unsigned long combined_idx;
 297                 struct free_area *area;
 298                 struct page *buddy;
 299
 300                 combined_idx = __find_combined_index(page_idx, order);
 301                 buddy = __page_find_buddy(page, page_idx, order);
 302
 303                 if (bad_range(zone, buddy))
 304                         break;
 305                 if (!page_is_buddy(buddy, order))
 306                         break;          /* Move the buddy up one level. */
 307                 list_del(&buddy->lru);
 308                 area = zone->free_area + order;
 309                 area->nr_free--;
 310                 rmv_page_order(buddy);
 311                 page = page + (combined_idx - page_idx);
 312                 page_idx = combined_idx;
 313                 order++;
 314         }
 315         set_page_order(page, order);
 316         list_add(&page->lru, &zone->free_area[order].free_list);
 317         zone->free_area[order].nr_free++;
 318 }
 319
 320 static inline void free_pages_check(const char *function, struct page *page)
 321 {
 322         if (    page_mapcount(page) ||
 323                 page->mapping != NULL ||
 324                 page_count(page) != 0 ||
 325                 (page->flags & (
 326                         1 << PG_lru     |
 327                         1 << PG_private |
 328                         1 << PG_locked  |
 329                         1 << PG_active  |
 330                         1 << PG_reclaim |
 331                         1 << PG_slab    |
 332                         1 << PG_swapcache |
 333                         1 << PG_writeback )))
 334                 bad_page(function, page);
 335         if (PageDirty(page))
 336                 ClearPageDirty(page);
 337 }
 338
 339 /*
 340  * Frees a list of pages.
 341  * Assumes all pages on list are in same zone, and of same order.
 342  * count is the number of pages to free, or 0 for all on the list.
 343  *
 344  * If the zone was previously in an "all pages pinned" state then look to
 345  * see if this freeing clears that state.
 346  *
 347  * And clear the zone's pages_scanned counter, to hold off the "all pages are
 348  * pinned" detection logic.
 349  */
 350 static int
 351 free_pages_bulk(struct zone *zone, int count,
 352                 struct list_head *list, unsigned int order)
 353 {
 354         unsigned long flags;
 355         struct page *page = NULL;
 356         int ret = 0;
 357
 358         spin_lock_irqsave(&zone->lock, flags);
 359         zone->all_unreclaimable = 0;
 360         zone->pages_scanned = 0;
 361         while (!list_empty(list) && count--) {
 362                 page = list_entry(list->prev, struct page, lru);
 363                 /* have to delete it as __free_pages_bulk list manipulates */
 364                 list_del(&page->lru);
 365                 __free_pages_bulk(page, zone, order);
 366                 ret++;
 367         }
 368         spin_unlock_irqrestore(&zone->lock, flags);
 369         return ret;
 370 }
 371
 372 void __free_pages_ok(struct page *page, unsigned int order)
 373 {
 374         LIST_HEAD(list);
 375         int i;
 376
 377         if (arch_free_page(page, order))
 378                 return;
 379
 380         mod_page_state(pgfree, 1 << order);
 381
 382 #ifndef CONFIG_MMU
 383         if (order > 0)
 384                 for (i = 1 ; i < (1 << order) ; ++i)
 385                         __put_page(page + i);
 386 #endif
 387
 388         for (i = 0 ; i < (1 << order) ; ++i)
 389                 free_pages_check(__FUNCTION__, page + i);
 390         list_add(&page->lru, &list);
 391         kernel_map_pages(page, 1<<order, 0);
 392         free_pages_bulk(page_zone(page), 1, &list, order);
 393 }
 394
 395
 396 /*
 397  * The order of subdivision here is critical for the IO subsystem.
 398  * Please do not alter this order without good reasons and regression
 399  * testing. Specifically, as large blocks of memory are subdivided,
 400  * the order in which smaller blocks are delivered depends on the order
 401  * they're subdivided in this function. This is the primary factor
 402  * influencing the order in which pages are delivered to the IO
 403  * subsystem according to empirical testing, and this is also justified
 404  * by considering the behavior of a buddy system containing a single
 405  * large block of memory acted on by a series of small allocations.
 406  * This behavior is a critical factor in sglist merging's success.
 407  *
 408  * -- wli
 409  */
 410 static inline struct page *
 411 expand(struct zone *zone, struct page *page,
 412         int low, int high, struct free_area *area)
 413 {
 414         unsigned long size = 1 << high;
 415
 416         while (high > low) {
 417                 area--;
 418                 high--;
 419                 size >>= 1;
 420                 BUG_ON(bad_range(zone, &page[size]));
 421                 list_add(&page[size].lru, &area->free_list);
 422                 area->nr_free++;
 423                 set_page_order(&page[size], high);
 424         }
 425         return page;
 426 }
 427
 428 void set_page_refs(struct page *page, int order)
 429 {
 430 #ifdef CONFIG_MMU
 431         set_page_count(page, 1);
 432 #else
 433         int i;
 434
 435         /*
 436          * We need to reference all the pages for this order, otherwise if
 437          * anyone accesses one of the pages with (get/put) it will be freed.
 438          * - eg: access_process_vm()
 439          */
 440         for (i = 0; i < (1 << order); i++)
 441                 set_page_count(page + i, 1);
 442 #endif /* CONFIG_MMU */
 443 }
 444
 445 /*
 446  * This page is about to be returned from the page allocator
 447  */
 448 static void prep_new_page(struct page *page, int order)
 449 {
 450         if (page->mapping || page_mapcount(page) ||
 451             (page->flags & (
 452                         1 << PG_private |
 453                         1 << PG_locked  |
 454                         1 << PG_lru     |
 455                         1 << PG_active  |
 456                         1 << PG_dirty   |
 457                         1 << PG_reclaim |
 458                         1 << PG_swapcache |
 459                         1 << PG_writeback )))
 460                 bad_page(__FUNCTION__, page);
 461
 462         page->flags &= ~(1 << PG_uptodate | 1 << PG_error |
 463                         1 << PG_referenced | 1 << PG_arch_1 |
 464                         1 << PG_checked | 1 << PG_mappedtodisk);
 465         page->private = 0;
 466         set_page_refs(page, order);
 467         kernel_map_pages(page, 1 << order, 1);
 468 }
 469
 470 /*
 471  * Do the hard work of removing an element from the buddy allocator.
 472  * Call me with the zone->lock already held.
 473  */
 474 static struct page *__rmqueue(struct zone *zone, unsigned int order)
 475 {
 476         struct free_area * area;
 477         unsigned int current_order;
 478         struct page *page;
 479
 480         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
 481                 area = zone->free_area + current_order;
 482                 if (list_empty(&area->free_list))
 483                         continue;
 484
 485                 page = list_entry(area->free_list.next, struct page, lru);
 486                 list_del(&page->lru);
 487                 rmv_page_order(page);
 488                 area->nr_free--;
 489                 zone->free_pages -= 1UL << order;
 490                 return expand(zone, page, order, current_order, area);
 491         }
 492
 493         return NULL;
 494 }
 495
 496 /*
 497  * Obtain a specified number of elements from the buddy allocator, all under
 498  * a single hold of the lock, for efficiency.  Add them to the supplied list.
 499  * Returns the number of new pages which were placed at *list.
 500  */
 501 static int rmqueue_bulk(struct zone *zone, unsigned int order,
 502                         unsigned long count, struct list_head *list)
 503 {
 504         unsigned long flags;
 505         int i;
 506         int allocated = 0;
 507         struct page *page;
 508
 509         spin_lock_irqsave(&zone->lock, flags);
 510         for (i = 0; i < count; ++i) {
 511                 page = __rmqueue(zone, order);
 512                 if (page == NULL)
 513                         break;
 514                 allocated++;
 515                 list_add_tail(&page->lru, list);
 516         }
 517         spin_unlock_irqrestore(&zone->lock, flags);
 518         return allocated;
 519 }
 520
 521 #if defined(CONFIG_PM) || defined(CONFIG_HOTPLUG_CPU)
 522 static void __drain_pages(unsigned int cpu)
 523 {
 524         struct zone *zone;
 525         int i;
 526
 527         for_each_zone(zone) {
 528                 struct per_cpu_pageset *pset;
 529
 530                 pset = &zone->pageset[cpu];
 531                 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) {
 532                         struct per_cpu_pages *pcp;
 533
 534                         pcp = &pset->pcp[i];
 535                         pcp->count -= free_pages_bulk(zone, pcp->count,
 536                                                 &pcp->list, 0);
 537                 }
 538         }
 539 }
 540 #endif /* CONFIG_PM || CONFIG_HOTPLUG_CPU */
 541
 542 #ifdef CONFIG_PM
 543
 544 void mark_free_pages(struct zone *zone)
 545 {
 546         unsigned long zone_pfn, flags;
 547         int order;
 548         struct list_head *curr;
 549
 550         if (!zone->spanned_pages)
 551                 return;
 552
 553         spin_lock_irqsave(&zone->lock, flags);
 554         for (zone_pfn = 0; zone_pfn < zone->spanned_pages; ++zone_pfn)
 555                 ClearPageNosaveFree(pfn_to_page(zone_pfn + zone->zone_start_pfn));
 556
 557         for (order = MAX_ORDER - 1; order >= 0; --order)
 558                 list_for_each(curr, &zone->free_area[order].free_list) {
 559                         unsigned long start_pfn, i;
 560
 561                         start_pfn = page_to_pfn(list_entry(curr, struct page, lru));
 562
 563                         for (i=0; i < (1<<order); i++)
 564                                 SetPageNosaveFree(pfn_to_page(start_pfn+i));
 565         }
 566         spin_unlock_irqrestore(&zone->lock, flags);
 567 }
 568
 569 /*
 570  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
 571  */
 572 void drain_local_pages(void)
 573 {
 574         unsigned long flags;
 575
 576         local_irq_save(flags);
 577         __drain_pages(smp_processor_id());
 578         local_irq_restore(flags);
 579 }
 580 #endif /* CONFIG_PM */
 581
 582 static void zone_statistics(struct zonelist *zonelist, struct zone *z)
 583 {
 584 #ifdef CONFIG_NUMA
 585         unsigned long flags;
 586         int cpu;
 587         pg_data_t *pg = z->zone_pgdat;
 588         pg_data_t *orig = zonelist->zones[0]->zone_pgdat;
 589         struct per_cpu_pageset *p;
 590
 591         local_irq_save(flags);
 592         cpu = smp_processor_id();
 593         p = &z->pageset[cpu];
 594         if (pg == orig) {
 595                 z->pageset[cpu].numa_hit++;
 596         } else {
 597                 p->numa_miss++;
 598                 zonelist->zones[0]->pageset[cpu].numa_foreign++;
 599         }
 600         if (pg == NODE_DATA(numa_node_id()))
 601                 p->local_node++;
 602         else
 603                 p->other_node++;
 604         local_irq_restore(flags);
 605 #endif
 606 }
 607
 608 /*
 609  * Free a 0-order page
 610  */
 611 static void FASTCALL(free_hot_cold_page(struct page *page, int cold));
 612 static void fastcall free_hot_cold_page(struct page *page, int cold)
 613 {
 614         struct zone *zone = page_zone(page);
 615         struct per_cpu_pages *pcp;
 616         unsigned long flags;
 617
 618         if (arch_free_page(page, 0))
 619                 return;
 620
 621         kernel_map_pages(page, 1, 0);
 622         inc_page_state(pgfree);
 623         if (PageAnon(page))
 624                 page->mapping = NULL;
 625         free_pages_check(__FUNCTION__, page);
 626         pcp = &zone->pageset[get_cpu()].pcp[cold];
 627         local_irq_save(flags);
 628         if (pcp->count >= pcp->high)
 629                 pcp->count -= free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
 630         list_add(&page->lru, &pcp->list);
 631         pcp->count++;
 632         local_irq_restore(flags);
 633         put_cpu();
 634 }
 635
 636 void fastcall free_hot_page(struct page *page)
 637 {
 638         free_hot_cold_page(page, 0);
 639 }
 640
 641 void fastcall free_cold_page(struct page *page)
 642 {
 643         free_hot_cold_page(page, 1);
 644 }
 645
 646 static inline void prep_zero_page(struct page *page, int order, unsigned int __nocast gfp_flags)
 647 {
 648         int i;
 649
 650         BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM);
 651         for(i = 0; i < (1 << order); i++)
 652                 clear_highpage(page + i);
 653 }
 654
 655 /*
 656  * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
 657  * we cheat by calling it from here, in the order > 0 path.  Saves a branch
 658  * or two.
 659  */
 660 static struct page *
 661 buffered_rmqueue(struct zone *zone, int order, unsigned int __nocast gfp_flags)
 662 {
 663         unsigned long flags;
 664         struct page *page = NULL;
 665         int cold = !!(gfp_flags & __GFP_COLD);
 666
 667         if (order == 0) {
 668                 struct per_cpu_pages *pcp;
 669
 670                 pcp = &zone->pageset[get_cpu()].pcp[cold];
 671                 local_irq_save(flags);
 672                 if (pcp->count <= pcp->low)
 673                         pcp->count += rmqueue_bulk(zone, 0,
 674                                                 pcp->batch, &pcp->list);
 675                 if (pcp->count) {
 676                         page = list_entry(pcp->list.next, struct page, lru);
 677                         list_del(&page->lru);
 678                         pcp->count--;
 679                 }
 680                 local_irq_restore(flags);
 681                 put_cpu();
 682         }
 683
 684         if (page == NULL) {
 685                 spin_lock_irqsave(&zone->lock, flags);
 686                 page = __rmqueue(zone, order);
 687                 spin_unlock_irqrestore(&zone->lock, flags);
 688         }
 689
 690         if (page != NULL) {
 691                 BUG_ON(bad_range(zone, page));
 692                 mod_page_state_zone(zone, pgalloc, 1 << order);
 693                 prep_new_page(page, order);
 694
 695                 if (gfp_flags & __GFP_ZERO)
 696                         prep_zero_page(page, order, gfp_flags);
 697
 698                 if (order && (gfp_flags & __GFP_COMP))
 699                         prep_compound_page(page, order);
 700         }
 701         return page;
 702 }
 703
 704 /*
 705  * Return 1 if free pages are above 'mark'. This takes into account the order
 706  * of the allocation.
 707  */
 708 int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
 709                       int classzone_idx, int can_try_harder, int gfp_high)
 710 {
 711         /* free_pages my go negative - that's OK */
 712         long min = mark, free_pages = z->free_pages - (1 << order) + 1;
 713         int o;
 714
 715         if (gfp_high)
 716                 min -= min / 2;
 717         if (can_try_harder)
 718                 min -= min / 4;
 719
 720         if (free_pages <= min + z->lowmem_reserve[classzone_idx])
 721                 return 0;
 722         for (o = 0; o < order; o++) {
 723                 /* At the next order, this order's pages become unavailable */
 724                 free_pages -= z->free_area[o].nr_free << o;
 725
 726                 /* Require fewer higher order pages to be free */
 727                 min >>= 1;
 728
 729                 if (free_pages <= min)
 730                         return 0;
 731         }
 732         return 1;
 733 }
 734
 735 /*
 736  * This is the 'heart' of the zoned buddy allocator.
 737  */
 738 struct page * fastcall
 739 __alloc_pages(unsigned int __nocast gfp_mask, unsigned int order,
 740                 struct zonelist *zonelist)
 741 {
 742         const int wait = gfp_mask & __GFP_WAIT;
 743         struct zone **zones, *z;
 744         struct page *page;
 745         struct reclaim_state reclaim_state;
 746         struct task_struct *p = current;
 747         int i;
 748         int classzone_idx;
 749         int do_retry;
 750         int can_try_harder;
 751         int did_some_progress;
 752
 753         might_sleep_if(wait);
 754
 755         /*
 756          * The caller may dip into page reserves a bit more if the caller
 757          * cannot run direct reclaim, or is the caller has realtime scheduling
 758          * policy
 759          */
 760         can_try_harder = (unlikely(rt_task(p)) && !in_interrupt()) || !wait;
 761
 762         zones = zonelist->zones;  /* the list of zones suitable for gfp_mask */
 763
 764         if (unlikely(zones[0] == NULL)) {
 765                 /* Should this ever happen?? */
 766                 return NULL;
 767         }
 768
 769         classzone_idx = zone_idx(zones[0]);
 770
 771  restart:
 772         /* Go through the zonelist once, looking for a zone with enough free */
 773         for (i = 0; (z = zones[i]) != NULL; i++) {
 774
 775                 if (!zone_watermark_ok(z, order, z->pages_low,
 776                                        classzone_idx, 0, 0))
 777                         continue;
 778
 779                 if (!cpuset_zone_allowed(z))
 780                         continue;
 781
 782                 page = buffered_rmqueue(z, order, gfp_mask);
 783                 if (page)
 784                         goto got_pg;
 785         }
 786
 787         for (i = 0; (z = zones[i]) != NULL; i++)
 788                 wakeup_kswapd(z, order);
 789
 790         /*
 791          * Go through the zonelist again. Let __GFP_HIGH and allocations
 792          * coming from realtime tasks to go deeper into reserves
 793          *
 794          * This is the last chance, in general, before the goto nopage.
 795          * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
 796          */
 797         for (i = 0; (z = zones[i]) != NULL; i++) {
 798                 if (!zone_watermark_ok(z, order, z->pages_min,
 799                                        classzone_idx, can_try_harder,
 800                                        gfp_mask & __GFP_HIGH))
 801                         continue;
 802
 803                 if (wait && !cpuset_zone_allowed(z))
 804                         continue;
 805
 806                 page = buffered_rmqueue(z, order, gfp_mask);
 807                 if (page)
 808                         goto got_pg;
 809         }
 810
 811         /* This allocation should allow future memory freeing. */
 812
 813         if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
 814                         && !in_interrupt()) {
 815                 if (!(gfp_mask & __GFP_NOMEMALLOC)) {
 816                         /* go through the zonelist yet again, ignoring mins */
 817                         for (i = 0; (z = zones[i]) != NULL; i++) {
 818                                 if (!cpuset_zone_allowed(z))
 819                                         continue;
 820                                 page = buffered_rmqueue(z, order, gfp_mask);
 821                                 if (page)
 822                                         goto got_pg;
 823                         }
 824                 }
 825                 goto nopage;
 826         }
 827
 828         /* Atomic allocations - we can't balance anything */
 829         if (!wait)
 830                 goto nopage;
 831
 832 rebalance:
 833         cond_resched();
 834
 835         /* We now go into synchronous reclaim */
 836         p->flags |= PF_MEMALLOC;
 837         reclaim_state.reclaimed_slab = 0;
 838         p->reclaim_state = &reclaim_state;
 839
 840         did_some_progress = try_to_free_pages(zones, gfp_mask, order);
 841
 842         p->reclaim_state = NULL;
 843         p->flags &= ~PF_MEMALLOC;
 844
 845         cond_resched();
 846
 847         if (likely(did_some_progress)) {
 848                 /*
 849                  * Go through the zonelist yet one more time, keep
 850                  * very high watermark here, this is only to catch
 851                  * a parallel oom killing, we must fail if we're still
 852                  * under heavy pressure.
 853                  */
 854                 for (i = 0; (z = zones[i]) != NULL; i++) {
 855                         if (!zone_watermark_ok(z, order, z->pages_min,
 856                                                classzone_idx, can_try_harder,
 857                                                gfp_mask & __GFP_HIGH))
 858                                 continue;
 859
 860                         if (!cpuset_zone_allowed(z))
 861                                 continue;
 862
 863                         page = buffered_rmqueue(z, order, gfp_mask);
 864                         if (page)
 865                                 goto got_pg;
 866                 }
 867         } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
 868                 /*
 869                  * Go through the zonelist yet one more time, keep
 870                  * very high watermark here, this is only to catch
 871                  * a parallel oom killing, we must fail if we're still
 872                  * under heavy pressure.
 873                  */
 874                 for (i = 0; (z = zones[i]) != NULL; i++) {
 875                         if (!zone_watermark_ok(z, order, z->pages_high,
 876                                                classzone_idx, 0, 0))
 877                                 continue;
 878
 879                         if (!cpuset_zone_allowed(z))
 880                                 continue;
 881
 882                         page = buffered_rmqueue(z, order, gfp_mask);
 883                         if (page)
 884                                 goto got_pg;
 885                 }
 886
 887                 out_of_memory(gfp_mask);
 888                 goto restart;
 889         }
 890
 891         /*
 892          * Don't let big-order allocations loop unless the caller explicitly
 893          * requests that.  Wait for some write requests to complete then retry.
 894          *
 895          * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order
 896          * <= 3, but that may not be true in other implementations.
 897          */
 898         do_retry = 0;
 899         if (!(gfp_mask & __GFP_NORETRY)) {
 900                 if ((order <= 3) || (gfp_mask & __GFP_REPEAT))
 901                         do_retry = 1;
 902                 if (gfp_mask & __GFP_NOFAIL)
 903                         do_retry = 1;
 904         }
 905         if (do_retry) {
 906                 blk_congestion_wait(WRITE, HZ/50);
 907                 goto rebalance;
 908         }
 909
 910 nopage:
 911         if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
 912                 printk(KERN_WARNING "%s: page allocation failure."
 913                         " order:%d, mode:0x%x\n",
 914                         p->comm, order, gfp_mask);
 915                 dump_stack();
 916         }
 917         return NULL;
 918 got_pg:
 919         zone_statistics(zonelist, z);
 920         return page;
 921 }
 922
 923 EXPORT_SYMBOL(__alloc_pages);
 924
 925 /*
 926  * Common helper functions.
 927  */
 928 fastcall unsigned long __get_free_pages(unsigned int __nocast gfp_mask, unsigned int order)
 929 {
 930         struct page * page;
 931         page = alloc_pages(gfp_mask, order);
 932         if (!page)
 933                 return 0;
 934         return (unsigned long) page_address(page);
 935 }
 936
 937 EXPORT_SYMBOL(__get_free_pages);
 938
 939 fastcall unsigned long get_zeroed_page(unsigned int __nocast gfp_mask)
 940 {
 941         struct page * page;
 942
 943         /*
 944          * get_zeroed_page() returns a 32-bit address, which cannot represent
 945          * a highmem page
 946          */
 947         BUG_ON(gfp_mask & __GFP_HIGHMEM);
 948
 949         page = alloc_pages(gfp_mask | __GFP_ZERO, 0);
 950         if (page)
 951                 return (unsigned long) page_address(page);
 952         return 0;
 953 }
 954
 955 EXPORT_SYMBOL(get_zeroed_page);
 956
 957 void __pagevec_free(struct pagevec *pvec)
 958 {
 959         int i = pagevec_count(pvec);
 960
 961         while (--i >= 0)
 962                 free_hot_cold_page(pvec->pages[i], pvec->cold);
 963 }
 964
 965 fastcall void __free_pages(struct page *page, unsigned int order)
 966 {
 967         if (!PageReserved(page) && put_page_testzero(page)) {
 968                 if (order == 0)
 969                         free_hot_page(page);
 970                 else
 971                         __free_pages_ok(page, order);
 972         }
 973 }
 974
 975 EXPORT_SYMBOL(__free_pages);
 976
 977 fastcall void free_pages(unsigned long addr, unsigned int order)
 978 {
 979         if (addr != 0) {
 980                 BUG_ON(!virt_addr_valid((void *)addr));
 981                 __free_pages(virt_to_page((void *)addr), order);
 982         }
 983 }
 984
 985 EXPORT_SYMBOL(free_pages);
 986
 987 /*
 988  * Total amount of free (allocatable) RAM:
 989  */
 990 unsigned int nr_free_pages(void)
 991 {
 992         unsigned int sum = 0;
 993         struct zone *zone;
 994
 995         for_each_zone(zone)
 996                 sum += zone->free_pages;
 997
 998         return sum;
 999 }
1000
1001 EXPORT_SYMBOL(nr_free_pages);
1002
1003 #ifdef CONFIG_NUMA
1004 unsigned int nr_free_pages_pgdat(pg_data_t *pgdat)
1005 {
1006         unsigned int i, sum = 0;
1007
1008         for (i = 0; i < MAX_NR_ZONES; i++)
1009                 sum += pgdat->node_zones[i].free_pages;
1010
1011         return sum;
1012 }
1013 #endif
1014
1015 static unsigned int nr_free_zone_pages(int offset)
1016 {
1017         pg_data_t *pgdat;
1018         unsigned int sum = 0;
1019
1020         for_each_pgdat(pgdat) {
1021                 struct zonelist *zonelist = pgdat->node_zonelists + offset;
1022                 struct zone **zonep = zonelist->zones;
1023                 struct zone *zone;
1024
1025                 for (zone = *zonep++; zone; zone = *zonep++) {
1026                         unsigned long size = zone->present_pages;
1027                         unsigned long high = zone->pages_high;
1028                         if (size > high)
1029                                 sum += size - high;
1030                 }
1031         }
1032
1033         return sum;
1034 }
1035
1036 /*
1037  * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
1038  */
1039 unsigned int nr_free_buffer_pages(void)
1040 {
1041         return nr_free_zone_pages(GFP_USER & GFP_ZONEMASK);
1042 }
1043
1044 /*
1045  * Amount of free RAM allocatable within all zones
1046  */
1047 unsigned int nr_free_pagecache_pages(void)
1048 {
1049         return nr_free_zone_pages(GFP_HIGHUSER & GFP_ZONEMASK);
1050 }
1051
1052 #ifdef CONFIG_HIGHMEM
1053 unsigned int nr_free_highpages (void)
1054 {
1055         pg_data_t *pgdat;
1056         unsigned int pages = 0;
1057
1058         for_each_pgdat(pgdat)
1059                 pages += pgdat->node_zones[ZONE_HIGHMEM].free_pages;
1060
1061         return pages;
1062 }
1063 #endif
1064
1065 #ifdef CONFIG_NUMA
1066 static void show_node(struct zone *zone)
1067 {
1068         printk("Node %d ", zone->zone_pgdat->node_id);
1069 }
1070 #else
1071 #define show_node(zone) do { } while (0)
1072 #endif
1073
1074 /*
1075  * Accumulate the page_state information across all CPUs.
1076  * The result is unavoidably approximate - it can change
1077  * during and after execution of this function.
1078  */
1079 static DEFINE_PER_CPU(struct page_state, page_states) = {0};
1080
1081 atomic_t nr_pagecache = ATOMIC_INIT(0);
1082 EXPORT_SYMBOL(nr_pagecache);
1083 #ifdef CONFIG_SMP
1084 DEFINE_PER_CPU(long, nr_pagecache_local) = 0;
1085 #endif
1086
1087 void __get_page_state(struct page_state *ret, int nr)
1088 {
1089         int cpu = 0;
1090
1091         memset(ret, 0, sizeof(*ret));
1092
1093         cpu = first_cpu(cpu_online_map);
1094         while (cpu < NR_CPUS) {
1095                 unsigned long *in, *out, off;
1096
1097                 in = (unsigned long *)&per_cpu(page_states, cpu);
1098
1099                 cpu = next_cpu(cpu, cpu_online_map);
1100
1101                 if (cpu < NR_CPUS)
1102                         prefetch(&per_cpu(page_states, cpu));
1103
1104                 out = (unsigned long *)ret;
1105                 for (off = 0; off < nr; off++)
1106                         *out++ += *in++;
1107         }
1108 }
1109
1110 void get_page_state(struct page_state *ret)
1111 {
1112         int nr;
1113
1114         nr = offsetof(struct page_state, GET_PAGE_STATE_LAST);
1115         nr /= sizeof(unsigned long);
1116
1117         __get_page_state(ret, nr + 1);
1118 }
1119
1120 void get_full_page_state(struct page_state *ret)
1121 {
1122         __get_page_state(ret, sizeof(*ret) / sizeof(unsigned long));
1123 }
1124
1125 unsigned long __read_page_state(unsigned offset)
1126 {
1127         unsigned long ret = 0;
1128         int cpu;
1129
1130         for_each_online_cpu(cpu) {
1131                 unsigned long in;
1132
1133                 in = (unsigned long)&per_cpu(page_states, cpu) + offset;
1134                 ret += *((unsigned long *)in);
1135         }
1136         return ret;
1137 }
1138
1139 void __mod_page_state(unsigned offset, unsigned long delta)
1140 {
1141         unsigned long flags;
1142         void* ptr;
1143
1144         local_irq_save(flags);
1145         ptr = &__get_cpu_var(page_states);
1146         *(unsigned long*)(ptr + offset) += delta;
1147         local_irq_restore(flags);
1148 }
1149
1150 EXPORT_SYMBOL(__mod_page_state);
1151
1152 void __get_zone_counts(unsigned long *active, unsigned long *inactive,
1153                         unsigned long *free, struct pglist_data *pgdat)
1154 {
1155         struct zone *zones = pgdat->node_zones;
1156         int i;
1157
1158         *active = 0;
1159         *inactive = 0;
1160         *free = 0;
1161         for (i = 0; i < MAX_NR_ZONES; i++) {
1162                 *active += zones[i].nr_active;
1163                 *inactive += zones[i].nr_inactive;
1164                 *free += zones[i].free_pages;
1165         }
1166 }
1167
1168 void get_zone_counts(unsigned long *active,
1169                 unsigned long *inactive, unsigned long *free)
1170 {
1171         struct pglist_data *pgdat;
1172
1173         *active = 0;
1174         *inactive = 0;
1175         *free = 0;
1176         for_each_pgdat(pgdat) {
1177                 unsigned long l, m, n;
1178                 __get_zone_counts(&l, &m, &n, pgdat);
1179                 *active += l;
1180                 *inactive += m;
1181                 *free += n;
1182         }
1183 }
1184
1185 void si_meminfo(struct sysinfo *val)
1186 {
1187         val->totalram = totalram_pages;
1188         val->sharedram = 0;
1189         val->freeram = nr_free_pages();
1190         val->bufferram = nr_blockdev_pages();
1191 #ifdef CONFIG_HIGHMEM
1192         val->totalhigh = totalhigh_pages;
1193         val->freehigh = nr_free_highpages();
1194 #else
1195         val->totalhigh = 0;
1196         val->freehigh = 0;
1197 #endif
1198         val->mem_unit = PAGE_SIZE;
1199         if (vx_flags(VXF_VIRT_MEM, 0))
1200                 vx_vsi_meminfo(val);
1201 }
1202
1203 EXPORT_SYMBOL(si_meminfo);
1204
1205 #ifdef CONFIG_NUMA
1206 void si_meminfo_node(struct sysinfo *val, int nid)
1207 {
1208         pg_data_t *pgdat = NODE_DATA(nid);
1209
1210         val->totalram = pgdat->node_present_pages;
1211         val->freeram = nr_free_pages_pgdat(pgdat);
1212         val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
1213         val->freehigh = pgdat->node_zones[ZONE_HIGHMEM].free_pages;
1214         val->mem_unit = PAGE_SIZE;
1215 }
1216 #endif
1217
1218 #define K(x) ((x) << (PAGE_SHIFT-10))
1219
1220 /*
1221  * Show free area list (used inside shift_scroll-lock stuff)
1222  * We also calculate the percentage fragmentation. We do this by counting the
1223  * memory on each free list with the exception of the first item on the list.
1224  */
1225 void show_free_areas(void)
1226 {
1227         struct page_state ps;
1228         int cpu, temperature;
1229         unsigned long active;
1230         unsigned long inactive;
1231         unsigned long free;
1232         struct zone *zone;
1233
1234         for_each_zone(zone) {
1235                 show_node(zone);
1236                 printk("%s per-cpu:", zone->name);
1237
1238                 if (!zone->present_pages) {
1239                         printk(" empty\n");
1240                         continue;
1241                 } else
1242                         printk("\n");
1243
1244                 for (cpu = 0; cpu < NR_CPUS; ++cpu) {
1245                         struct per_cpu_pageset *pageset;
1246
1247                         if (!cpu_possible(cpu))
1248                                 continue;
1249
1250                         pageset = zone->pageset + cpu;
1251
1252                         for (temperature = 0; temperature < 2; temperature++)
1253                                 printk("cpu %d %s: low %d, high %d, batch %d\n",
1254                                         cpu,
1255                                         temperature ? "cold" : "hot",
1256                                         pageset->pcp[temperature].low,
1257                                         pageset->pcp[temperature].high,
1258                                         pageset->pcp[temperature].batch);
1259                 }
1260         }
1261
1262         get_page_state(&ps);
1263         get_zone_counts(&active, &inactive, &free);
1264
1265         printk("\nFree pages: %11ukB (%ukB HighMem)\n",
1266                 K(nr_free_pages()),
1267                 K(nr_free_highpages()));
1268
1269         printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu "
1270                 "unstable:%lu free:%u slab:%lu mapped:%lu pagetables:%lu\n",
1271                 active,
1272                 inactive,
1273                 ps.nr_dirty,
1274                 ps.nr_writeback,
1275                 ps.nr_unstable,
1276                 nr_free_pages(),
1277                 ps.nr_slab,
1278                 ps.nr_mapped,
1279                 ps.nr_page_table_pages);
1280
1281         for_each_zone(zone) {
1282                 int i;
1283
1284                 show_node(zone);
1285                 printk("%s"
1286                         " free:%lukB"
1287                         " min:%lukB"
1288                         " low:%lukB"
1289                         " high:%lukB"
1290                         " active:%lukB"
1291                         " inactive:%lukB"
1292                         " present:%lukB"
1293                         " pages_scanned:%lu"
1294                         " all_unreclaimable? %s"
1295                         "\n",
1296                         zone->name,
1297                         K(zone->free_pages),
1298                         K(zone->pages_min),
1299                         K(zone->pages_low),
1300                         K(zone->pages_high),
1301                         K(zone->nr_active),
1302                         K(zone->nr_inactive),
1303                         K(zone->present_pages),
1304                         zone->pages_scanned,
1305                         (zone->all_unreclaimable ? "yes" : "no")
1306                         );
1307                 printk("lowmem_reserve[]:");
1308                 for (i = 0; i < MAX_NR_ZONES; i++)
1309                         printk(" %lu", zone->lowmem_reserve[i]);
1310                 printk("\n");
1311         }
1312
1313         for_each_zone(zone) {
1314                 unsigned long nr, flags, order, total = 0;
1315
1316                 show_node(zone);
1317                 printk("%s: ", zone->name);
1318                 if (!zone->present_pages) {
1319                         printk("empty\n");
1320                         continue;
1321                 }
1322
1323                 spin_lock_irqsave(&zone->lock, flags);
1324                 for (order = 0; order < MAX_ORDER; order++) {
1325                         nr = zone->free_area[order].nr_free;
1326                         total += nr << order;
1327                         printk("%lu*%lukB ", nr, K(1UL) << order);
1328                 }
1329                 spin_unlock_irqrestore(&zone->lock, flags);
1330                 printk("= %lukB\n", K(total));
1331         }
1332
1333         show_swap_cache_info();
1334 }
1335
1336 /*
1337  * Builds allocation fallback zone lists.
1338  */
1339 static int __init build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist, int j, int k)
1340 {
1341         switch (k) {
1342                 struct zone *zone;
1343         default:
1344                 BUG();
1345         case ZONE_HIGHMEM:
1346                 zone = pgdat->node_zones + ZONE_HIGHMEM;
1347                 if (zone->present_pages) {
1348 #ifndef CONFIG_HIGHMEM
1349                         BUG();
1350 #endif
1351                         zonelist->zones[j++] = zone;
1352                 }
1353         case ZONE_NORMAL:
1354                 zone = pgdat->node_zones + ZONE_NORMAL;
1355                 if (zone->present_pages)
1356                         zonelist->zones[j++] = zone;
1357         case ZONE_DMA:
1358                 zone = pgdat->node_zones + ZONE_DMA;
1359                 if (zone->present_pages)
1360                         zonelist->zones[j++] = zone;
1361         }
1362
1363         return j;
1364 }
1365
1366 #ifdef CONFIG_NUMA
1367 #define MAX_NODE_LOAD (num_online_nodes())
1368 static int __initdata node_load[MAX_NUMNODES];
1369 /**
1370  * find_next_best_node - find the next node that should appear in a given node's fallback list
1371  * @node: node whose fallback list we're appending
1372  * @used_node_mask: nodemask_t of already used nodes
1373  *
1374  * We use a number of factors to determine which is the next node that should
1375  * appear on a given node's fallback list.  The node should not have appeared
1376  * already in @node's fallback list, and it should be the next closest node
1377  * according to the distance array (which contains arbitrary distance values
1378  * from each node to each node in the system), and should also prefer nodes
1379  * with no CPUs, since presumably they'll have very little allocation pressure
1380  * on them otherwise.
1381  * It returns -1 if no node is found.
1382  */
1383 static int __init find_next_best_node(int node, nodemask_t *used_node_mask)
1384 {
1385         int i, n, val;
1386         int min_val = INT_MAX;
1387         int best_node = -1;
1388
1389         for_each_online_node(i) {
1390                 cpumask_t tmp;
1391
1392                 /* Start from local node */
1393                 n = (node+i) % num_online_nodes();
1394
1395                 /* Don't want a node to appear more than once */
1396                 if (node_isset(n, *used_node_mask))
1397                         continue;
1398
1399                 /* Use the local node if we haven't already */
1400                 if (!node_isset(node, *used_node_mask)) {
1401                         best_node = node;
1402                         break;
1403                 }
1404
1405                 /* Use the distance array to find the distance */
1406                 val = node_distance(node, n);
1407
1408                 /* Give preference to headless and unused nodes */
1409                 tmp = node_to_cpumask(n);
1410                 if (!cpus_empty(tmp))
1411                         val += PENALTY_FOR_NODE_WITH_CPUS;
1412
1413                 /* Slight preference for less loaded node */
1414                 val *= (MAX_NODE_LOAD*MAX_NUMNODES);
1415                 val += node_load[n];
1416
1417                 if (val < min_val) {
1418                         min_val = val;
1419                         best_node = n;
1420                 }
1421         }
1422
1423         if (best_node >= 0)
1424                 node_set(best_node, *used_node_mask);
1425
1426         return best_node;
1427 }
1428
1429 static void __init build_zonelists(pg_data_t *pgdat)
1430 {
1431         int i, j, k, node, local_node;
1432         int prev_node, load;
1433         struct zonelist *zonelist;
1434         nodemask_t used_mask;
1435
1436         /* initialize zonelists */
1437         for (i = 0; i < GFP_ZONETYPES; i++) {
1438                 zonelist = pgdat->node_zonelists + i;
1439                 zonelist->zones[0] = NULL;
1440         }
1441
1442         /* NUMA-aware ordering of nodes */
1443         local_node = pgdat->node_id;
1444         load = num_online_nodes();
1445         prev_node = local_node;
1446         nodes_clear(used_mask);
1447         while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
1448                 /*
1449                  * We don't want to pressure a particular node.
1450                  * So adding penalty to the first node in same
1451                  * distance group to make it round-robin.
1452                  */
1453                 if (node_distance(local_node, node) !=
1454                                 node_distance(local_node, prev_node))
1455                         node_load[node] += load;
1456                 prev_node = node;
1457                 load--;
1458                 for (i = 0; i < GFP_ZONETYPES; i++) {
1459                         zonelist = pgdat->node_zonelists + i;
1460                         for (j = 0; zonelist->zones[j] != NULL; j++);
1461
1462                         k = ZONE_NORMAL;
1463                         if (i & __GFP_HIGHMEM)
1464                                 k = ZONE_HIGHMEM;
1465                         if (i & __GFP_DMA)
1466                                 k = ZONE_DMA;
1467
1468                         j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
1469                         zonelist->zones[j] = NULL;
1470                 }
1471         }
1472 }
1473
1474 #else   /* CONFIG_NUMA */
1475
1476 static void __init build_zonelists(pg_data_t *pgdat)
1477 {
1478         int i, j, k, node, local_node;
1479
1480         local_node = pgdat->node_id;
1481         for (i = 0; i < GFP_ZONETYPES; i++) {
1482                 struct zonelist *zonelist;
1483
1484                 zonelist = pgdat->node_zonelists + i;
1485
1486                 j = 0;
1487                 k = ZONE_NORMAL;
1488                 if (i & __GFP_HIGHMEM)
1489                         k = ZONE_HIGHMEM;
1490                 if (i & __GFP_DMA)
1491                         k = ZONE_DMA;
1492
1493                 j = build_zonelists_node(pgdat, zonelist, j, k);
1494                 /*
1495                  * Now we build the zonelist so that it contains the zones
1496                  * of all the other nodes.
1497                  * We don't want to pressure a particular node, so when
1498                  * building the zones for node N, we make sure that the
1499                  * zones coming right after the local ones are those from
1500                  * node N+1 (modulo N)
1501                  */
1502                 for (node = local_node + 1; node < MAX_NUMNODES; node++) {
1503                         if (!node_online(node))
1504                                 continue;
1505                         j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
1506                 }
1507                 for (node = 0; node < local_node; node++) {
1508                         if (!node_online(node))
1509                                 continue;
1510                         j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
1511                 }
1512
1513                 zonelist->zones[j] = NULL;
1514         }
1515 }
1516
1517 #endif  /* CONFIG_NUMA */
1518
1519 void __init build_all_zonelists(void)
1520 {
1521         int i;
1522
1523         for_each_online_node(i)
1524                 build_zonelists(NODE_DATA(i));
1525         printk("Built %i zonelists\n", num_online_nodes());
1526         cpuset_init_current_mems_allowed();
1527 }
1528
1529 /*
1530  * Helper functions to size the waitqueue hash table.
1531  * Essentially these want to choose hash table sizes sufficiently
1532  * large so that collisions trying to wait on pages are rare.
1533  * But in fact, the number of active page waitqueues on typical
1534  * systems is ridiculously low, less than 200. So this is even
1535  * conservative, even though it seems large.
1536  *
1537  * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
1538  * waitqueues, i.e. the size of the waitq table given the number of pages.
1539  */
1540 #define PAGES_PER_WAITQUEUE     256
1541
1542 static inline unsigned long wait_table_size(unsigned long pages)
1543 {
1544         unsigned long size = 1;
1545
1546         pages /= PAGES_PER_WAITQUEUE;
1547
1548         while (size < pages)
1549                 size <<= 1;
1550
1551         /*
1552          * Once we have dozens or even hundreds of threads sleeping
1553          * on IO we've got bigger problems than wait queue collision.
1554          * Limit the size of the wait table to a reasonable size.
1555          */
1556         size = min(size, 4096UL);
1557
1558         return max(size, 4UL);
1559 }
1560
1561 /*
1562  * This is an integer logarithm so that shifts can be used later
1563  * to extract the more random high bits from the multiplicative
1564  * hash function before the remainder is taken.
1565  */
1566 static inline unsigned long wait_table_bits(unsigned long size)
1567 {
1568         return ffz(~size);
1569 }
1570
1571 #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
1572
1573 static void __init calculate_zone_totalpages(struct pglist_data *pgdat,
1574                 unsigned long *zones_size, unsigned long *zholes_size)
1575 {
1576         unsigned long realtotalpages, totalpages = 0;
1577         int i;
1578
1579         for (i = 0; i < MAX_NR_ZONES; i++)
1580                 totalpages += zones_size[i];
1581         pgdat->node_spanned_pages = totalpages;
1582
1583         realtotalpages = totalpages;
1584         if (zholes_size)
1585                 for (i = 0; i < MAX_NR_ZONES; i++)
1586                         realtotalpages -= zholes_size[i];
1587         pgdat->node_present_pages = realtotalpages;
1588         printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id, realtotalpages);
1589 }
1590
1591
1592 /*
1593  * Initially all pages are reserved - free ones are freed
1594  * up by free_all_bootmem() once the early boot process is
1595  * done. Non-atomic initialization, single-pass.
1596  */
1597 void __init memmap_init_zone(unsigned long size, int nid, unsigned long zone,
1598                 unsigned long start_pfn)
1599 {
1600         struct page *start = pfn_to_page(start_pfn);
1601         struct page *page;
1602
1603         for (page = start; page < (start + size); page++) {
1604                 set_page_zone(page, NODEZONE(nid, zone));
1605                 set_page_count(page, 0);
1606                 reset_page_mapcount(page);
1607                 SetPageReserved(page);
1608                 INIT_LIST_HEAD(&page->lru);
1609 #ifdef WANT_PAGE_VIRTUAL
1610                 /* The shift won't overflow because ZONE_NORMAL is below 4G. */
1611                 if (!is_highmem_idx(zone))
1612                         set_page_address(page, __va(start_pfn << PAGE_SHIFT));
1613 #endif
1614                 start_pfn++;
1615         }
1616 }
1617
1618 void zone_init_free_lists(struct pglist_data *pgdat, struct zone *zone,
1619                                 unsigned long size)
1620 {
1621         int order;
1622         for (order = 0; order < MAX_ORDER ; order++) {
1623                 INIT_LIST_HEAD(&zone->free_area[order].free_list);
1624                 zone->free_area[order].nr_free = 0;
1625         }
1626 }
1627
1628 #ifndef __HAVE_ARCH_MEMMAP_INIT
1629 #define memmap_init(size, nid, zone, start_pfn) \
1630         memmap_init_zone((size), (nid), (zone), (start_pfn))
1631 #endif
1632
1633 /*
1634  * Set up the zone data structures:
1635  *   - mark all pages reserved
1636  *   - mark all memory queues empty
1637  *   - clear the memory bitmaps
1638  */
1639 static void __init free_area_init_core(struct pglist_data *pgdat,
1640                 unsigned long *zones_size, unsigned long *zholes_size)
1641 {
1642         unsigned long i, j;
1643         const unsigned long zone_required_alignment = 1UL << (MAX_ORDER-1);
1644         int cpu, nid = pgdat->node_id;
1645         unsigned long zone_start_pfn = pgdat->node_start_pfn;
1646
1647         pgdat->nr_zones = 0;
1648         init_waitqueue_head(&pgdat->kswapd_wait);
1649         pgdat->kswapd_max_order = 0;
1650
1651         for (j = 0; j < MAX_NR_ZONES; j++) {
1652                 struct zone *zone = pgdat->node_zones + j;
1653                 unsigned long size, realsize;
1654                 unsigned long batch;
1655
1656                 zone_table[NODEZONE(nid, j)] = zone;
1657                 realsize = size = zones_size[j];
1658                 if (zholes_size)
1659                         realsize -= zholes_size[j];
1660
1661                 if (j == ZONE_DMA || j == ZONE_NORMAL)
1662                         nr_kernel_pages += realsize;
1663                 nr_all_pages += realsize;
1664
1665                 zone->spanned_pages = size;
1666                 zone->present_pages = realsize;
1667                 zone->name = zone_names[j];
1668                 spin_lock_init(&zone->lock);
1669                 spin_lock_init(&zone->lru_lock);
1670                 zone->zone_pgdat = pgdat;
1671                 zone->free_pages = 0;
1672
1673                 zone->temp_priority = zone->prev_priority = DEF_PRIORITY;
1674
1675                 /*
1676                  * The per-cpu-pages pools are set to around 1000th of the
1677                  * size of the zone.  But no more than 1/4 of a meg - there's
1678                  * no point in going beyond the size of L2 cache.
1679                  *
1680                  * OK, so we don't know how big the cache is.  So guess.
1681                  */
1682                 batch = zone->present_pages / 1024;
1683                 if (batch * PAGE_SIZE > 256 * 1024)
1684                         batch = (256 * 1024) / PAGE_SIZE;
1685                 batch /= 4;             /* We effectively *= 4 below */
1686                 if (batch < 1)
1687                         batch = 1;
1688
1689                 /*
1690                  * Clamp the batch to a 2^n - 1 value. Having a power
1691                  * of 2 value was found to be more likely to have
1692                  * suboptimal cache aliasing properties in some cases.
1693                  *
1694                  * For example if 2 tasks are alternately allocating
1695                  * batches of pages, one task can end up with a lot
1696                  * of pages of one half of the possible page colors
1697                  * and the other with pages of the other colors.
1698                  */
1699                 batch = (1 << fls(batch + batch/2)) - 1;
1700
1701                 for (cpu = 0; cpu < NR_CPUS; cpu++) {
1702                         struct per_cpu_pages *pcp;
1703
1704                         pcp = &zone->pageset[cpu].pcp[0];       /* hot */
1705                         pcp->count = 0;
1706                         pcp->low = 2 * batch;
1707                         pcp->high = 6 * batch;
1708                         pcp->batch = 1 * batch;
1709                         INIT_LIST_HEAD(&pcp->list);
1710
1711                         pcp = &zone->pageset[cpu].pcp[1];       /* cold */
1712                         pcp->count = 0;
1713                         pcp->low = 0;
1714                         pcp->high = 2 * batch;
1715                         pcp->batch = 1 * batch;
1716                         INIT_LIST_HEAD(&pcp->list);
1717                 }
1718                 printk(KERN_DEBUG "  %s zone: %lu pages, LIFO batch:%lu\n",
1719                                 zone_names[j], realsize, batch);
1720                 INIT_LIST_HEAD(&zone->active_list);
1721                 INIT_LIST_HEAD(&zone->inactive_list);
1722                 zone->nr_scan_active = 0;
1723                 zone->nr_scan_inactive = 0;
1724                 zone->nr_active = 0;
1725                 zone->nr_inactive = 0;
1726                 if (!size)
1727                         continue;
1728
1729                 /*
1730                  * The per-page waitqueue mechanism uses hashed waitqueues
1731                  * per zone.
1732                  */
1733                 zone->wait_table_size = wait_table_size(size);
1734                 zone->wait_table_bits =
1735                         wait_table_bits(zone->wait_table_size);
1736                 zone->wait_table = (wait_queue_head_t *)
1737                         alloc_bootmem_node(pgdat, zone->wait_table_size
1738                                                 * sizeof(wait_queue_head_t));
1739
1740                 for(i = 0; i < zone->wait_table_size; ++i)
1741                         init_waitqueue_head(zone->wait_table + i);
1742
1743                 pgdat->nr_zones = j+1;
1744
1745                 zone->zone_mem_map = pfn_to_page(zone_start_pfn);
1746                 zone->zone_start_pfn = zone_start_pfn;
1747
1748                 if ((zone_start_pfn) & (zone_required_alignment-1))
1749                         printk(KERN_CRIT "BUG: wrong zone alignment, it will crash\n");
1750
1751                 memmap_init(size, nid, j, zone_start_pfn);
1752
1753                 zone_start_pfn += size;
1754
1755                 zone_init_free_lists(pgdat, zone, zone->spanned_pages);
1756         }
1757 }
1758
1759 static void __init alloc_node_mem_map(struct pglist_data *pgdat)
1760 {
1761         unsigned long size;
1762
1763         /* Skip empty nodes */
1764         if (!pgdat->node_spanned_pages)
1765                 return;
1766
1767         /* ia64 gets its own node_mem_map, before this, without bootmem */
1768         if (!pgdat->node_mem_map) {
1769                 size = (pgdat->node_spanned_pages + 1) * sizeof(struct page);
1770                 pgdat->node_mem_map = alloc_bootmem_node(pgdat, size);
1771         }
1772 #ifndef CONFIG_DISCONTIGMEM
1773         /*
1774          * With no DISCONTIG, the global mem_map is just set as node 0's
1775          */
1776         if (pgdat == NODE_DATA(0))
1777                 mem_map = NODE_DATA(0)->node_mem_map;
1778 #endif
1779 }
1780
1781 void __init free_area_init_node(int nid, struct pglist_data *pgdat,
1782                 unsigned long *zones_size, unsigned long node_start_pfn,
1783                 unsigned long *zholes_size)
1784 {
1785         pgdat->node_id = nid;
1786         pgdat->node_start_pfn = node_start_pfn;
1787         calculate_zone_totalpages(pgdat, zones_size, zholes_size);
1788
1789         alloc_node_mem_map(pgdat);
1790
1791         free_area_init_core(pgdat, zones_size, zholes_size);
1792 }
1793
1794 #ifndef CONFIG_DISCONTIGMEM
1795 static bootmem_data_t contig_bootmem_data;
1796 struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data };
1797
1798 EXPORT_SYMBOL(contig_page_data);
1799
1800 void __init free_area_init(unsigned long *zones_size)
1801 {
1802         free_area_init_node(0, &contig_page_data, zones_size,
1803                         __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
1804 }
1805 #endif
1806
1807 #ifdef CONFIG_PROC_FS
1808
1809 #include <linux/seq_file.h>
1810
1811 static void *frag_start(struct seq_file *m, loff_t *pos)
1812 {
1813         pg_data_t *pgdat;
1814         loff_t node = *pos;
1815
1816         for (pgdat = pgdat_list; pgdat && node; pgdat = pgdat->pgdat_next)
1817                 --node;
1818
1819         return pgdat;
1820 }
1821
1822 static void *frag_next(struct seq_file *m, void *arg, loff_t *pos)
1823 {
1824         pg_data_t *pgdat = (pg_data_t *)arg;
1825
1826         (*pos)++;
1827         return pgdat->pgdat_next;
1828 }
1829
1830 static void frag_stop(struct seq_file *m, void *arg)
1831 {
1832 }
1833
1834 /*
1835  * This walks the free areas for each zone.
1836  */
1837 static int frag_show(struct seq_file *m, void *arg)
1838 {
1839         pg_data_t *pgdat = (pg_data_t *)arg;
1840         struct zone *zone;
1841         struct zone *node_zones = pgdat->node_zones;
1842         unsigned long flags;
1843         int order;
1844
1845         for (zone = node_zones; zone - node_zones < MAX_NR_ZONES; ++zone) {
1846                 if (!zone->present_pages)
1847                         continue;
1848
1849                 spin_lock_irqsave(&zone->lock, flags);
1850                 seq_printf(m, "Node %d, zone %8s ", pgdat->node_id, zone->name);
1851                 for (order = 0; order < MAX_ORDER; ++order)
1852                         seq_printf(m, "%6lu ", zone->free_area[order].nr_free);
1853                 spin_unlock_irqrestore(&zone->lock, flags);
1854                 seq_putc(m, '\n');
1855         }
1856         return 0;
1857 }
1858
1859 struct seq_operations fragmentation_op = {
1860         .start  = frag_start,
1861         .next   = frag_next,
1862         .stop   = frag_stop,
1863         .show   = frag_show,
1864 };
1865
1866 static char *vmstat_text[] = {
1867         "nr_dirty",
1868         "nr_writeback",
1869         "nr_unstable",
1870         "nr_page_table_pages",
1871         "nr_mapped",
1872         "nr_slab",
1873
1874         "pgpgin",
1875         "pgpgout",
1876         "pswpin",
1877         "pswpout",
1878         "pgalloc_high",
1879
1880         "pgalloc_normal",
1881         "pgalloc_dma",
1882         "pgfree",
1883         "pgactivate",
1884         "pgdeactivate",
1885
1886         "pgfault",
1887         "pgmajfault",
1888         "pgrefill_high",
1889         "pgrefill_normal",
1890         "pgrefill_dma",
1891
1892         "pgsteal_high",
1893         "pgsteal_normal",
1894         "pgsteal_dma",
1895         "pgscan_kswapd_high",
1896         "pgscan_kswapd_normal",
1897
1898         "pgscan_kswapd_dma",
1899         "pgscan_direct_high",
1900         "pgscan_direct_normal",
1901         "pgscan_direct_dma",
1902         "pginodesteal",
1903
1904         "slabs_scanned",
1905         "kswapd_steal",
1906         "kswapd_inodesteal",
1907         "pageoutrun",
1908         "allocstall",
1909
1910         "pgrotated",
1911         "nr_bounce",
1912 };
1913
1914 static void *vmstat_start(struct seq_file *m, loff_t *pos)
1915 {
1916         struct page_state *ps;
1917
1918         if (*pos >= ARRAY_SIZE(vmstat_text))
1919                 return NULL;
1920
1921         ps = kmalloc(sizeof(*ps), GFP_KERNEL);
1922         m->private = ps;
1923         if (!ps)
1924                 return ERR_PTR(-ENOMEM);
1925         get_full_page_state(ps);
1926         ps->pgpgin /= 2;                /* sectors -> kbytes */
1927         ps->pgpgout /= 2;
1928         return (unsigned long *)ps + *pos;
1929 }
1930
1931 static void *vmstat_next(struct seq_file *m, void *arg, loff_t *pos)
1932 {
1933         (*pos)++;
1934         if (*pos >= ARRAY_SIZE(vmstat_text))
1935                 return NULL;
1936         return (unsigned long *)m->private + *pos;
1937 }
1938
1939 static int vmstat_show(struct seq_file *m, void *arg)
1940 {
1941         unsigned long *l = arg;
1942         unsigned long off = l - (unsigned long *)m->private;
1943
1944         seq_printf(m, "%s %lu\n", vmstat_text[off], *l);
1945         return 0;
1946 }
1947
1948 static void vmstat_stop(struct seq_file *m, void *arg)
1949 {
1950         kfree(m->private);
1951         m->private = NULL;
1952 }
1953
1954 struct seq_operations vmstat_op = {
1955         .start  = vmstat_start,
1956         .next   = vmstat_next,
1957         .stop   = vmstat_stop,
1958         .show   = vmstat_show,
1959 };
1960
1961 #endif /* CONFIG_PROC_FS */
1962
1963 #ifdef CONFIG_HOTPLUG_CPU
1964 static int page_alloc_cpu_notify(struct notifier_block *self,
1965                                  unsigned long action, void *hcpu)
1966 {
1967         int cpu = (unsigned long)hcpu;
1968         long *count;
1969         unsigned long *src, *dest;
1970
1971         if (action == CPU_DEAD) {
1972                 int i;
1973
1974                 /* Drain local pagecache count. */
1975                 count = &per_cpu(nr_pagecache_local, cpu);
1976                 atomic_add(*count, &nr_pagecache);
1977                 *count = 0;
1978                 local_irq_disable();
1979                 __drain_pages(cpu);
1980
1981                 /* Add dead cpu's page_states to our own. */
1982                 dest = (unsigned long *)&__get_cpu_var(page_states);
1983                 src = (unsigned long *)&per_cpu(page_states, cpu);
1984
1985                 for (i = 0; i < sizeof(struct page_state)/sizeof(unsigned long);
1986                                 i++) {
1987                         dest[i] += src[i];
1988                         src[i] = 0;
1989                 }
1990
1991                 local_irq_enable();
1992         }
1993         return NOTIFY_OK;
1994 }
1995 #endif /* CONFIG_HOTPLUG_CPU */
1996
1997 void __init page_alloc_init(void)
1998 {
1999         hotcpu_notifier(page_alloc_cpu_notify, 0);
2000 }
2001
2002 /*
2003  * setup_per_zone_lowmem_reserve - called whenever
2004  *      sysctl_lower_zone_reserve_ratio changes.  Ensures that each zone
2005  *      has a correct pages reserved value, so an adequate number of
2006  *      pages are left in the zone after a successful __alloc_pages().
2007  */
2008 static void setup_per_zone_lowmem_reserve(void)
2009 {
2010         struct pglist_data *pgdat;
2011         int j, idx;
2012
2013         for_each_pgdat(pgdat) {
2014                 for (j = 0; j < MAX_NR_ZONES; j++) {
2015                         struct zone *zone = pgdat->node_zones + j;
2016                         unsigned long present_pages = zone->present_pages;
2017
2018                         zone->lowmem_reserve[j] = 0;
2019
2020                         for (idx = j-1; idx >= 0; idx--) {
2021                                 struct zone *lower_zone;
2022
2023                                 if (sysctl_lowmem_reserve_ratio[idx] < 1)
2024                                         sysctl_lowmem_reserve_ratio[idx] = 1;
2025
2026                                 lower_zone = pgdat->node_zones + idx;
2027                                 lower_zone->lowmem_reserve[j] = present_pages /
2028                                         sysctl_lowmem_reserve_ratio[idx];
2029                                 present_pages += lower_zone->present_pages;
2030                         }
2031                 }
2032         }
2033 }
2034
2035 /*
2036  * setup_per_zone_pages_min - called when min_free_kbytes changes.  Ensures
2037  *      that the pages_{min,low,high} values for each zone are set correctly
2038  *      with respect to min_free_kbytes.
2039  */
2040 static void setup_per_zone_pages_min(void)
2041 {
2042         unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
2043         unsigned long lowmem_pages = 0;
2044         struct zone *zone;
2045         unsigned long flags;
2046
2047         /* Calculate total number of !ZONE_HIGHMEM pages */
2048         for_each_zone(zone) {
2049                 if (!is_highmem(zone))
2050                         lowmem_pages += zone->present_pages;
2051         }
2052
2053         for_each_zone(zone) {
2054                 spin_lock_irqsave(&zone->lru_lock, flags);
2055                 if (is_highmem(zone)) {
2056                         /*
2057                          * Often, highmem doesn't need to reserve any pages.
2058                          * But the pages_min/low/high values are also used for
2059                          * batching up page reclaim activity so we need a
2060                          * decent value here.
2061                          */
2062                         int min_pages;
2063
2064                         min_pages = zone->present_pages / 1024;
2065                         if (min_pages < SWAP_CLUSTER_MAX)
2066                                 min_pages = SWAP_CLUSTER_MAX;
2067                         if (min_pages > 128)
2068                                 min_pages = 128;
2069                         zone->pages_min = min_pages;
2070                 } else {
2071                         /* if it's a lowmem zone, reserve a number of pages
2072                          * proportionate to the zone's size.
2073                          */
2074                         zone->pages_min = (pages_min * zone->present_pages) /
2075                                            lowmem_pages;
2076                 }
2077
2078                 /*
2079                  * When interpreting these watermarks, just keep in mind that:
2080                  * zone->pages_min == (zone->pages_min * 4) / 4;
2081                  */
2082                 zone->pages_low   = (zone->pages_min * 5) / 4;
2083                 zone->pages_high  = (zone->pages_min * 6) / 4;
2084                 spin_unlock_irqrestore(&zone->lru_lock, flags);
2085         }
2086 }
2087
2088 /*
2089  * Initialise min_free_kbytes.
2090  *
2091  * For small machines we want it small (128k min).  For large machines
2092  * we want it large (64MB max).  But it is not linear, because network
2093  * bandwidth does not increase linearly with machine size.  We use
2094  *
2095  *      min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
2096  *      min_free_kbytes = sqrt(lowmem_kbytes * 16)
2097  *
2098  * which yields
2099  *
2100  * 16MB:        512k
2101  * 32MB:        724k
2102  * 64MB:        1024k
2103  * 128MB:       1448k
2104  * 256MB:       2048k
2105  * 512MB:       2896k
2106  * 1024MB:      4096k
2107  * 2048MB:      5792k
2108  * 4096MB:      8192k
2109  * 8192MB:      11584k
2110  * 16384MB:     16384k
2111  */
2112 static int __init init_per_zone_pages_min(void)
2113 {
2114         unsigned long lowmem_kbytes;
2115
2116         lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
2117
2118         min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
2119         if (min_free_kbytes < 128)
2120                 min_free_kbytes = 128;
2121         if (min_free_kbytes > 65536)
2122                 min_free_kbytes = 65536;
2123         setup_per_zone_pages_min();
2124         setup_per_zone_lowmem_reserve();
2125         return 0;
2126 }
2127 module_init(init_per_zone_pages_min)
2128
2129 /*
2130  * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so
2131  *      that we can call two helper functions whenever min_free_kbytes
2132  *      changes.
2133  */
2134 int min_free_kbytes_sysctl_handler(ctl_table *table, int write,
2135         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
2136 {
2137         proc_dointvec(table, write, file, buffer, length, ppos);
2138         setup_per_zone_pages_min();
2139         return 0;
2140 }
2141
2142 /*
2143  * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
2144  *      proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
2145  *      whenever sysctl_lowmem_reserve_ratio changes.
2146  *
2147  * The reserve ratio obviously has absolutely no relation with the
2148  * pages_min watermarks. The lowmem reserve ratio can only make sense
2149  * if in function of the boot time zone sizes.
2150  */
2151 int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write,
2152         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
2153 {
2154         proc_dointvec_minmax(table, write, file, buffer, length, ppos);
2155         setup_per_zone_lowmem_reserve();
2156         return 0;
2157 }
2158
2159 __initdata int hashdist = HASHDIST_DEFAULT;
2160
2161 #ifdef CONFIG_NUMA
2162 static int __init set_hashdist(char *str)
2163 {
2164         if (!str)
2165                 return 0;
2166         hashdist = simple_strtoul(str, &str, 0);
2167         return 1;
2168 }
2169 __setup("hashdist=", set_hashdist);
2170 #endif
2171
2172 /*
2173  * allocate a large system hash table from bootmem
2174  * - it is assumed that the hash table must contain an exact power-of-2
2175  *   quantity of entries
2176  * - limit is the number of hash buckets, not the total allocation size
2177  */
2178 void *__init alloc_large_system_hash(const char *tablename,
2179                                      unsigned long bucketsize,
2180                                      unsigned long numentries,
2181                                      int scale,
2182                                      int flags,
2183                                      unsigned int *_hash_shift,
2184                                      unsigned int *_hash_mask,
2185                                      unsigned long limit)
2186 {
2187         unsigned long long max = limit;
2188         unsigned long log2qty, size;
2189         void *table = NULL;
2190
2191         /* allow the kernel cmdline to have a say */
2192         if (!numentries) {
2193                 /* round applicable memory size up to nearest megabyte */
2194                 numentries = (flags & HASH_HIGHMEM) ? nr_all_pages : nr_kernel_pages;
2195                 numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
2196                 numentries >>= 20 - PAGE_SHIFT;
2197                 numentries <<= 20 - PAGE_SHIFT;
2198
2199                 /* limit to 1 bucket per 2^scale bytes of low memory */
2200                 if (scale > PAGE_SHIFT)
2201                         numentries >>= (scale - PAGE_SHIFT);
2202                 else
2203                         numentries <<= (PAGE_SHIFT - scale);
2204         }
2205         /* rounded up to nearest power of 2 in size */
2206         numentries = 1UL << (long_log2(numentries) + 1);
2207
2208         /* limit allocation size to 1/16 total memory by default */
2209         if (max == 0) {
2210                 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
2211                 do_div(max, bucketsize);
2212         }
2213
2214         if (numentries > max)
2215                 numentries = max;
2216
2217         log2qty = long_log2(numentries);
2218
2219         do {
2220                 size = bucketsize << log2qty;
2221                 if (flags & HASH_EARLY)
2222                         table = alloc_bootmem(size);
2223                 else if (hashdist)
2224                         table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
2225                 else {
2226                         unsigned long order;
2227                         for (order = 0; ((1UL << order) << PAGE_SHIFT) < size; order++)
2228                                 ;
2229                         table = (void*) __get_free_pages(GFP_ATOMIC, order);
2230                 }
2231         } while (!table && size > PAGE_SIZE && --log2qty);
2232
2233         if (!table)
2234                 panic("Failed to allocate %s hash table\n", tablename);
2235
2236         printk("%s hash table entries: %d (order: %d, %lu bytes)\n",
2237                tablename,
2238                (1U << log2qty),
2239                long_log2(size) - PAGE_SHIFT,
2240                size);
2241
2242         if (_hash_shift)
2243                 *_hash_shift = log2qty;
2244         if (_hash_mask)
2245                 *_hash_mask = (1 << log2qty) - 1;
2246
2247         return table;
2248 }