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