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