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