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 unsigned long __read_page_state(unsigned offset)
 992 {
 993         unsigned long ret = 0;
 994         int cpu;
 995
 996         for (cpu = 0; cpu < NR_CPUS; cpu++) {
 997                 unsigned long in;
 998
 999                 if (!cpu_possible(cpu))
1000                         continue;
1001
1002                 in = (unsigned long)&per_cpu(page_states, cpu) + offset;
1003                 ret += *((unsigned long *)in);
1004         }
1005         return ret;
1006 }
1007
1008 void get_zone_counts(unsigned long *active,
1009                 unsigned long *inactive, unsigned long *free)
1010 {
1011         struct zone *zone;
1012
1013         *active = 0;
1014         *inactive = 0;
1015         *free = 0;
1016         for_each_zone(zone) {
1017                 *active += zone->nr_active;
1018                 *inactive += zone->nr_inactive;
1019                 *free += zone->free_pages;
1020         }
1021 }
1022
1023 void si_meminfo(struct sysinfo *val)
1024 {
1025         val->totalram = totalram_pages;
1026         val->sharedram = 0;
1027         val->freeram = nr_free_pages();
1028         val->bufferram = nr_blockdev_pages();
1029 #ifdef CONFIG_HIGHMEM
1030         val->totalhigh = totalhigh_pages;
1031         val->freehigh = nr_free_highpages();
1032 #else
1033         val->totalhigh = 0;
1034         val->freehigh = 0;
1035 #endif
1036         val->mem_unit = PAGE_SIZE;
1037 }
1038
1039 EXPORT_SYMBOL(si_meminfo);
1040
1041 #ifdef CONFIG_NUMA
1042 void si_meminfo_node(struct sysinfo *val, int nid)
1043 {
1044         pg_data_t *pgdat = NODE_DATA(nid);
1045
1046         val->totalram = pgdat->node_present_pages;
1047         val->freeram = nr_free_pages_pgdat(pgdat);
1048         val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
1049         val->freehigh = pgdat->node_zones[ZONE_HIGHMEM].free_pages;
1050         val->mem_unit = PAGE_SIZE;
1051 }
1052 #endif
1053
1054 #define K(x) ((x) << (PAGE_SHIFT-10))
1055
1056 /*
1057  * Show free area list (used inside shift_scroll-lock stuff)
1058  * We also calculate the percentage fragmentation. We do this by counting the
1059  * memory on each free list with the exception of the first item on the list.
1060  */
1061 void show_free_areas(void)
1062 {
1063         struct page_state ps;
1064         int cpu, temperature;
1065         unsigned long active;
1066         unsigned long inactive;
1067         unsigned long free;
1068         struct zone *zone;
1069
1070         for_each_zone(zone) {
1071                 show_node(zone);
1072                 printk("%s per-cpu:", zone->name);
1073
1074                 if (!zone->present_pages) {
1075                         printk(" empty\n");
1076                         continue;
1077                 } else
1078                         printk("\n");
1079
1080                 for (cpu = 0; cpu < NR_CPUS; ++cpu) {
1081                         struct per_cpu_pageset *pageset;
1082
1083                         if (!cpu_possible(cpu))
1084                                 continue;
1085
1086                         pageset = zone->pageset + cpu;
1087
1088                         for (temperature = 0; temperature < 2; temperature++)
1089                                 printk("cpu %d %s: low %d, high %d, batch %d\n",
1090                                         cpu,
1091                                         temperature ? "cold" : "hot",
1092                                         pageset->pcp[temperature].low,
1093                                         pageset->pcp[temperature].high,
1094                                         pageset->pcp[temperature].batch);
1095                 }
1096         }
1097
1098         get_page_state(&ps);
1099         get_zone_counts(&active, &inactive, &free);
1100
1101         printk("\nFree pages: %11ukB (%ukB HighMem)\n",
1102                 K(nr_free_pages()),
1103                 K(nr_free_highpages()));
1104
1105         printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu "
1106                 "unstable:%lu free:%u slab:%lu mapped:%lu pagetables:%lu\n",
1107                 active,
1108                 inactive,
1109                 ps.nr_dirty,
1110                 ps.nr_writeback,
1111                 ps.nr_unstable,
1112                 nr_free_pages(),
1113                 ps.nr_slab,
1114                 ps.nr_mapped,
1115                 ps.nr_page_table_pages);
1116
1117         for_each_zone(zone) {
1118                 int i;
1119
1120                 show_node(zone);
1121                 printk("%s"
1122                         " free:%lukB"
1123                         " min:%lukB"
1124                         " low:%lukB"
1125                         " high:%lukB"
1126                         " active:%lukB"
1127                         " inactive:%lukB"
1128                         " present:%lukB"
1129                         "\n",
1130                         zone->name,
1131                         K(zone->free_pages),
1132                         K(zone->pages_min),
1133                         K(zone->pages_low),
1134                         K(zone->pages_high),
1135                         K(zone->nr_active),
1136                         K(zone->nr_inactive),
1137                         K(zone->present_pages)
1138                         );
1139                 printk("protections[]:");
1140                 for (i = 0; i < MAX_NR_ZONES; i++)
1141                         printk(" %lu", zone->protection[i]);
1142                 printk("\n");
1143         }
1144
1145         for_each_zone(zone) {
1146                 struct list_head *elem;
1147                 unsigned long nr, flags, order, total = 0;
1148
1149                 show_node(zone);
1150                 printk("%s: ", zone->name);
1151                 if (!zone->present_pages) {
1152                         printk("empty\n");
1153                         continue;
1154                 }
1155
1156                 spin_lock_irqsave(&zone->lock, flags);
1157                 for (order = 0; order < MAX_ORDER; order++) {
1158                         nr = 0;
1159                         list_for_each(elem, &zone->free_area[order].free_list)
1160                                 ++nr;
1161                         total += nr << order;
1162                         printk("%lu*%lukB ", nr, K(1UL) << order);
1163                 }
1164                 spin_unlock_irqrestore(&zone->lock, flags);
1165                 printk("= %lukB\n", K(total));
1166         }
1167
1168         show_swap_cache_info();
1169 }
1170
1171 /*
1172  * Builds allocation fallback zone lists.
1173  */
1174 static int __init build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist, int j, int k)
1175 {
1176         switch (k) {
1177                 struct zone *zone;
1178         default:
1179                 BUG();
1180         case ZONE_HIGHMEM:
1181                 zone = pgdat->node_zones + ZONE_HIGHMEM;
1182                 if (zone->present_pages) {
1183 #ifndef CONFIG_HIGHMEM
1184                         BUG();
1185 #endif
1186                         zonelist->zones[j++] = zone;
1187                 }
1188         case ZONE_NORMAL:
1189                 zone = pgdat->node_zones + ZONE_NORMAL;
1190                 if (zone->present_pages)
1191                         zonelist->zones[j++] = zone;
1192         case ZONE_DMA:
1193                 zone = pgdat->node_zones + ZONE_DMA;
1194                 if (zone->present_pages)
1195                         zonelist->zones[j++] = zone;
1196         }
1197
1198         return j;
1199 }
1200
1201 #ifdef CONFIG_NUMA
1202 #define MAX_NODE_LOAD (numnodes)
1203 static int __initdata node_load[MAX_NUMNODES];
1204 /**
1205  * find_next_best_node - find the next node that should appear in a given
1206  *    node's fallback list
1207  * @node: node whose fallback list we're appending
1208  * @used_node_mask: pointer to the bitmap of already used nodes
1209  *
1210  * We use a number of factors to determine which is the next node that should
1211  * appear on a given node's fallback list.  The node should not have appeared
1212  * already in @node's fallback list, and it should be the next closest node
1213  * according to the distance array (which contains arbitrary distance values
1214  * from each node to each node in the system), and should also prefer nodes
1215  * with no CPUs, since presumably they'll have very little allocation pressure
1216  * on them otherwise.
1217  * It returns -1 if no node is found.
1218  */
1219 static int __init find_next_best_node(int node, void *used_node_mask)
1220 {
1221         int i, n, val;
1222         int min_val = INT_MAX;
1223         int best_node = -1;
1224
1225         for (i = 0; i < numnodes; i++) {
1226                 cpumask_t tmp;
1227
1228                 /* Start from local node */
1229                 n = (node+i)%numnodes;
1230
1231                 /* Don't want a node to appear more than once */
1232                 if (test_bit(n, used_node_mask))
1233                         continue;
1234
1235                 /* Use the distance array to find the distance */
1236                 val = node_distance(node, n);
1237
1238                 /* Give preference to headless and unused nodes */
1239                 tmp = node_to_cpumask(n);
1240                 if (!cpus_empty(tmp))
1241                         val += PENALTY_FOR_NODE_WITH_CPUS;
1242
1243                 /* Slight preference for less loaded node */
1244                 val *= (MAX_NODE_LOAD*MAX_NUMNODES);
1245                 val += node_load[n];
1246
1247                 if (val < min_val) {
1248                         min_val = val;
1249                         best_node = n;
1250                 }
1251         }
1252
1253         if (best_node >= 0)
1254                 set_bit(best_node, used_node_mask);
1255
1256         return best_node;
1257 }
1258
1259 static void __init build_zonelists(pg_data_t *pgdat)
1260 {
1261         int i, j, k, node, local_node;
1262         int prev_node, load;
1263         struct zonelist *zonelist;
1264         DECLARE_BITMAP(used_mask, MAX_NUMNODES);
1265
1266         /* initialize zonelists */
1267         for (i = 0; i < MAX_NR_ZONES; i++) {
1268                 zonelist = pgdat->node_zonelists + i;
1269                 memset(zonelist, 0, sizeof(*zonelist));
1270                 zonelist->zones[0] = NULL;
1271         }
1272
1273         /* NUMA-aware ordering of nodes */
1274         local_node = pgdat->node_id;
1275         load = numnodes;
1276         prev_node = local_node;
1277         bitmap_zero(used_mask, MAX_NUMNODES);
1278         while ((node = find_next_best_node(local_node, used_mask)) >= 0) {
1279                 /*
1280                  * We don't want to pressure a particular node.
1281                  * So adding penalty to the first node in same
1282                  * distance group to make it round-robin.
1283                  */
1284                 if (node_distance(local_node, node) !=
1285                                 node_distance(local_node, prev_node))
1286                         node_load[node] += load;
1287                 prev_node = node;
1288                 load--;
1289                 for (i = 0; i < MAX_NR_ZONES; i++) {
1290                         zonelist = pgdat->node_zonelists + i;
1291                         for (j = 0; zonelist->zones[j] != NULL; j++);
1292
1293                         k = ZONE_NORMAL;
1294                         if (i & __GFP_HIGHMEM)
1295                                 k = ZONE_HIGHMEM;
1296                         if (i & __GFP_DMA)
1297                                 k = ZONE_DMA;
1298
1299                         j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
1300                         zonelist->zones[j] = NULL;
1301                 }
1302         }
1303 }
1304
1305 #else   /* CONFIG_NUMA */
1306
1307 static void __init build_zonelists(pg_data_t *pgdat)
1308 {
1309         int i, j, k, node, local_node;
1310
1311         local_node = pgdat->node_id;
1312         for (i = 0; i < MAX_NR_ZONES; i++) {
1313                 struct zonelist *zonelist;
1314
1315                 zonelist = pgdat->node_zonelists + i;
1316                 memset(zonelist, 0, sizeof(*zonelist));
1317
1318                 j = 0;
1319                 k = ZONE_NORMAL;
1320                 if (i & __GFP_HIGHMEM)
1321                         k = ZONE_HIGHMEM;
1322                 if (i & __GFP_DMA)
1323                         k = ZONE_DMA;
1324
1325                 j = build_zonelists_node(pgdat, zonelist, j, k);
1326                 /*
1327                  * Now we build the zonelist so that it contains the zones
1328                  * of all the other nodes.
1329                  * We don't want to pressure a particular node, so when
1330                  * building the zones for node N, we make sure that the
1331                  * zones coming right after the local ones are those from
1332                  * node N+1 (modulo N)
1333                  */
1334                 for (node = local_node + 1; node < numnodes; node++)
1335                         j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
1336                 for (node = 0; node < local_node; node++)
1337                         j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
1338
1339                 zonelist->zones[j] = NULL;
1340         }
1341 }
1342
1343 #endif  /* CONFIG_NUMA */
1344
1345 void __init build_all_zonelists(void)
1346 {
1347         int i;
1348
1349         for(i = 0 ; i < numnodes ; i++)
1350                 build_zonelists(NODE_DATA(i));
1351         printk("Built %i zonelists\n", numnodes);
1352 }
1353
1354 /*
1355  * Helper functions to size the waitqueue hash table.
1356  * Essentially these want to choose hash table sizes sufficiently
1357  * large so that collisions trying to wait on pages are rare.
1358  * But in fact, the number of active page waitqueues on typical
1359  * systems is ridiculously low, less than 200. So this is even
1360  * conservative, even though it seems large.
1361  *
1362  * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
1363  * waitqueues, i.e. the size of the waitq table given the number of pages.
1364  */
1365 #define PAGES_PER_WAITQUEUE     256
1366
1367 static inline unsigned long wait_table_size(unsigned long pages)
1368 {
1369         unsigned long size = 1;
1370
1371         pages /= PAGES_PER_WAITQUEUE;
1372
1373         while (size < pages)
1374                 size <<= 1;
1375
1376         /*
1377          * Once we have dozens or even hundreds of threads sleeping
1378          * on IO we've got bigger problems than wait queue collision.
1379          * Limit the size of the wait table to a reasonable size.
1380          */
1381         size = min(size, 4096UL);
1382
1383         return max(size, 4UL);
1384 }
1385
1386 /*
1387  * This is an integer logarithm so that shifts can be used later
1388  * to extract the more random high bits from the multiplicative
1389  * hash function before the remainder is taken.
1390  */
1391 static inline unsigned long wait_table_bits(unsigned long size)
1392 {
1393         return ffz(~size);
1394 }
1395
1396 #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
1397
1398 static void __init calculate_zone_totalpages(struct pglist_data *pgdat,
1399                 unsigned long *zones_size, unsigned long *zholes_size)
1400 {
1401         unsigned long realtotalpages, totalpages = 0;
1402         int i;
1403
1404         for (i = 0; i < MAX_NR_ZONES; i++)
1405                 totalpages += zones_size[i];
1406         pgdat->node_spanned_pages = totalpages;
1407
1408         realtotalpages = totalpages;
1409         if (zholes_size)
1410                 for (i = 0; i < MAX_NR_ZONES; i++)
1411                         realtotalpages -= zholes_size[i];
1412         pgdat->node_present_pages = realtotalpages;
1413         printk("On node %d totalpages: %lu\n", pgdat->node_id, realtotalpages);
1414 }
1415
1416
1417 /*
1418  * Initially all pages are reserved - free ones are freed
1419  * up by free_all_bootmem() once the early boot process is
1420  * done. Non-atomic initialization, single-pass.
1421  */
1422 void __init memmap_init_zone(struct page *start, unsigned long size, int nid,
1423                 unsigned long zone, unsigned long start_pfn)
1424 {
1425         struct page *page;
1426
1427         for (page = start; page < (start + size); page++) {
1428                 set_page_zone(page, NODEZONE(nid, zone));
1429                 set_page_count(page, 0);
1430                 SetPageReserved(page);
1431                 INIT_LIST_HEAD(&page->lru);
1432 #ifdef WANT_PAGE_VIRTUAL
1433                 /* The shift won't overflow because ZONE_NORMAL is below 4G. */
1434                 if (zone != ZONE_HIGHMEM)
1435                         set_page_address(page, __va(start_pfn << PAGE_SHIFT));
1436 #endif
1437                 start_pfn++;
1438         }
1439 }
1440
1441 #ifndef __HAVE_ARCH_MEMMAP_INIT
1442 #define memmap_init(start, size, nid, zone, start_pfn) \
1443         memmap_init_zone((start), (size), (nid), (zone), (start_pfn))
1444 #endif
1445
1446 /*
1447  * Set up the zone data structures:
1448  *   - mark all pages reserved
1449  *   - mark all memory queues empty
1450  *   - clear the memory bitmaps
1451  */
1452 static void __init free_area_init_core(struct pglist_data *pgdat,
1453                 unsigned long *zones_size, unsigned long *zholes_size)
1454 {
1455         unsigned long i, j;
1456         const unsigned long zone_required_alignment = 1UL << (MAX_ORDER-1);
1457         int cpu, nid = pgdat->node_id;
1458         struct page *lmem_map = pgdat->node_mem_map;
1459         unsigned long zone_start_pfn = pgdat->node_start_pfn;
1460
1461         pgdat->nr_zones = 0;
1462         init_waitqueue_head(&pgdat->kswapd_wait);
1463
1464         for (j = 0; j < MAX_NR_ZONES; j++) {
1465                 struct zone *zone = pgdat->node_zones + j;
1466                 unsigned long size, realsize;
1467                 unsigned long batch;
1468
1469                 zone_table[NODEZONE(nid, j)] = zone;
1470                 realsize = size = zones_size[j];
1471                 if (zholes_size)
1472                         realsize -= zholes_size[j];
1473
1474                 zone->spanned_pages = size;
1475                 zone->present_pages = realsize;
1476                 zone->name = zone_names[j];
1477                 spin_lock_init(&zone->lock);
1478                 spin_lock_init(&zone->lru_lock);
1479                 zone->zone_pgdat = pgdat;
1480                 zone->free_pages = 0;
1481
1482                 zone->temp_priority = zone->prev_priority = DEF_PRIORITY;
1483
1484                 /*
1485                  * The per-cpu-pages pools are set to around 1000th of the
1486                  * size of the zone.  But no more than 1/4 of a meg - there's
1487                  * no point in going beyond the size of L2 cache.
1488                  *
1489                  * OK, so we don't know how big the cache is.  So guess.
1490                  */
1491                 batch = zone->present_pages / 1024;
1492                 if (batch * PAGE_SIZE > 256 * 1024)
1493                         batch = (256 * 1024) / PAGE_SIZE;
1494                 batch /= 4;             /* We effectively *= 4 below */
1495                 if (batch < 1)
1496                         batch = 1;
1497
1498                 for (cpu = 0; cpu < NR_CPUS; cpu++) {
1499                         struct per_cpu_pages *pcp;
1500
1501                         pcp = &zone->pageset[cpu].pcp[0];       /* hot */
1502                         pcp->count = 0;
1503                         pcp->low = 2 * batch;
1504                         pcp->high = 6 * batch;
1505                         pcp->batch = 1 * batch;
1506                         INIT_LIST_HEAD(&pcp->list);
1507
1508                         pcp = &zone->pageset[cpu].pcp[1];       /* cold */
1509                         pcp->count = 0;
1510                         pcp->low = 0;
1511                         pcp->high = 2 * batch;
1512                         pcp->batch = 1 * batch;
1513                         INIT_LIST_HEAD(&pcp->list);
1514                 }
1515                 printk("  %s zone: %lu pages, LIFO batch:%lu\n",
1516                                 zone_names[j], realsize, batch);
1517                 INIT_LIST_HEAD(&zone->active_list);
1518                 INIT_LIST_HEAD(&zone->inactive_list);
1519                 atomic_set(&zone->nr_scan_active, 0);
1520                 atomic_set(&zone->nr_scan_inactive, 0);
1521                 zone->nr_active = 0;
1522                 zone->nr_inactive = 0;
1523                 if (!size)
1524                         continue;
1525
1526                 /*
1527                  * The per-page waitqueue mechanism uses hashed waitqueues
1528                  * per zone.
1529                  */
1530                 zone->wait_table_size = wait_table_size(size);
1531                 zone->wait_table_bits =
1532                         wait_table_bits(zone->wait_table_size);
1533                 zone->wait_table = (wait_queue_head_t *)
1534                         alloc_bootmem_node(pgdat, zone->wait_table_size
1535                                                 * sizeof(wait_queue_head_t));
1536
1537                 for(i = 0; i < zone->wait_table_size; ++i)
1538                         init_waitqueue_head(zone->wait_table + i);
1539
1540                 pgdat->nr_zones = j+1;
1541
1542                 zone->zone_mem_map = lmem_map;
1543                 zone->zone_start_pfn = zone_start_pfn;
1544
1545                 if ((zone_start_pfn) & (zone_required_alignment-1))
1546                         printk("BUG: wrong zone alignment, it will crash\n");
1547
1548                 memmap_init(lmem_map, size, nid, j, zone_start_pfn);
1549
1550                 zone_start_pfn += size;
1551                 lmem_map += size;
1552
1553                 for (i = 0; ; i++) {
1554                         unsigned long bitmap_size;
1555
1556                         INIT_LIST_HEAD(&zone->free_area[i].free_list);
1557                         if (i == MAX_ORDER-1) {
1558                                 zone->free_area[i].map = NULL;
1559                                 break;
1560                         }
1561
1562                         /*
1563                          * Page buddy system uses "index >> (i+1)",
1564                          * where "index" is at most "size-1".
1565                          *
1566                          * The extra "+3" is to round down to byte
1567                          * size (8 bits per byte assumption). Thus
1568                          * we get "(size-1) >> (i+4)" as the last byte
1569                          * we can access.
1570                          *
1571                          * The "+1" is because we want to round the
1572                          * byte allocation up rather than down. So
1573                          * we should have had a "+7" before we shifted
1574                          * down by three. Also, we have to add one as
1575                          * we actually _use_ the last bit (it's [0,n]
1576                          * inclusive, not [0,n[).
1577                          *
1578                          * So we actually had +7+1 before we shift
1579                          * down by 3. But (n+8) >> 3 == (n >> 3) + 1
1580                          * (modulo overflows, which we do not have).
1581                          *
1582                          * Finally, we LONG_ALIGN because all bitmap
1583                          * operations are on longs.
1584                          */
1585                         bitmap_size = (size-1) >> (i+4);
1586                         bitmap_size = LONG_ALIGN(bitmap_size+1);
1587                         zone->free_area[i].map =
1588                           (unsigned long *) alloc_bootmem_node(pgdat, bitmap_size);
1589                 }
1590         }
1591 }
1592
1593 void __init free_area_init_node(int nid, struct pglist_data *pgdat,
1594                 struct page *node_mem_map, unsigned long *zones_size,
1595                 unsigned long node_start_pfn, unsigned long *zholes_size)
1596 {
1597         unsigned long size;
1598
1599         pgdat->node_id = nid;
1600         pgdat->node_start_pfn = node_start_pfn;
1601         calculate_zone_totalpages(pgdat, zones_size, zholes_size);
1602         if (!node_mem_map) {
1603                 size = (pgdat->node_spanned_pages + 1) * sizeof(struct page);
1604                 node_mem_map = alloc_bootmem_node(pgdat, size);
1605         }
1606         pgdat->node_mem_map = node_mem_map;
1607
1608         free_area_init_core(pgdat, zones_size, zholes_size);
1609 }
1610
1611 #ifndef CONFIG_DISCONTIGMEM
1612 static bootmem_data_t contig_bootmem_data;
1613 struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data };
1614
1615 EXPORT_SYMBOL(contig_page_data);
1616
1617 void __init free_area_init(unsigned long *zones_size)
1618 {
1619         free_area_init_node(0, &contig_page_data, NULL, zones_size,
1620                         __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
1621         mem_map = contig_page_data.node_mem_map;
1622 }
1623 #endif
1624
1625 #ifdef CONFIG_PROC_FS
1626
1627 #include <linux/seq_file.h>
1628
1629 static void *frag_start(struct seq_file *m, loff_t *pos)
1630 {
1631         pg_data_t *pgdat;
1632         loff_t node = *pos;
1633
1634         for (pgdat = pgdat_list; pgdat && node; pgdat = pgdat->pgdat_next)
1635                 --node;
1636
1637         return pgdat;
1638 }
1639
1640 static void *frag_next(struct seq_file *m, void *arg, loff_t *pos)
1641 {
1642         pg_data_t *pgdat = (pg_data_t *)arg;
1643
1644         (*pos)++;
1645         return pgdat->pgdat_next;
1646 }
1647
1648 static void frag_stop(struct seq_file *m, void *arg)
1649 {
1650 }
1651
1652 /*
1653  * This walks the freelist for each zone. Whilst this is slow, I'd rather
1654  * be slow here than slow down the fast path by keeping stats - mjbligh
1655  */
1656 static int frag_show(struct seq_file *m, void *arg)
1657 {
1658         pg_data_t *pgdat = (pg_data_t *)arg;
1659         struct zone *zone;
1660         struct zone *node_zones = pgdat->node_zones;
1661         unsigned long flags;
1662         int order;
1663
1664         for (zone = node_zones; zone - node_zones < MAX_NR_ZONES; ++zone) {
1665                 if (!zone->present_pages)
1666                         continue;
1667
1668                 spin_lock_irqsave(&zone->lock, flags);
1669                 seq_printf(m, "Node %d, zone %8s ", pgdat->node_id, zone->name);
1670                 for (order = 0; order < MAX_ORDER; ++order) {
1671                         unsigned long nr_bufs = 0;
1672                         struct list_head *elem;
1673
1674                         list_for_each(elem, &(zone->free_area[order].free_list))
1675                                 ++nr_bufs;
1676                         seq_printf(m, "%6lu ", nr_bufs);
1677                 }
1678                 spin_unlock_irqrestore(&zone->lock, flags);
1679                 seq_putc(m, '\n');
1680         }
1681         return 0;
1682 }
1683
1684 struct seq_operations fragmentation_op = {
1685         .start  = frag_start,
1686         .next   = frag_next,
1687         .stop   = frag_stop,
1688         .show   = frag_show,
1689 };
1690
1691 static char *vmstat_text[] = {
1692         "nr_dirty",
1693         "nr_writeback",
1694         "nr_unstable",
1695         "nr_page_table_pages",
1696         "nr_mapped",
1697         "nr_slab",
1698
1699         "pgpgin",
1700         "pgpgout",
1701         "pswpin",
1702         "pswpout",
1703         "pgalloc_high",
1704
1705         "pgalloc_normal",
1706         "pgalloc_dma",
1707         "pgfree",
1708         "pgactivate",
1709         "pgdeactivate",
1710
1711         "pgfault",
1712         "pgmajfault",
1713         "pgrefill_high",
1714         "pgrefill_normal",
1715         "pgrefill_dma",
1716
1717         "pgsteal_high",
1718         "pgsteal_normal",
1719         "pgsteal_dma",
1720         "pgscan_kswapd_high",
1721         "pgscan_kswapd_normal",
1722
1723         "pgscan_kswapd_dma",
1724         "pgscan_direct_high",
1725         "pgscan_direct_normal",
1726         "pgscan_direct_dma",
1727         "pginodesteal",
1728
1729         "slabs_scanned",
1730         "kswapd_steal",
1731         "kswapd_inodesteal",
1732         "pageoutrun",
1733         "allocstall",
1734
1735         "pgrotated",
1736 };
1737
1738 static void *vmstat_start(struct seq_file *m, loff_t *pos)
1739 {
1740         struct page_state *ps;
1741
1742         if (*pos >= ARRAY_SIZE(vmstat_text))
1743                 return NULL;
1744
1745         ps = kmalloc(sizeof(*ps), GFP_KERNEL);
1746         m->private = ps;
1747         if (!ps)
1748                 return ERR_PTR(-ENOMEM);
1749         get_full_page_state(ps);
1750         ps->pgpgin /= 2;                /* sectors -> kbytes */
1751         ps->pgpgout /= 2;
1752         return (unsigned long *)ps + *pos;
1753 }
1754
1755 static void *vmstat_next(struct seq_file *m, void *arg, loff_t *pos)
1756 {
1757         (*pos)++;
1758         if (*pos >= ARRAY_SIZE(vmstat_text))
1759                 return NULL;
1760         return (unsigned long *)m->private + *pos;
1761 }
1762
1763 static int vmstat_show(struct seq_file *m, void *arg)
1764 {
1765         unsigned long *l = arg;
1766         unsigned long off = l - (unsigned long *)m->private;
1767
1768         seq_printf(m, "%s %lu\n", vmstat_text[off], *l);
1769         return 0;
1770 }
1771
1772 static void vmstat_stop(struct seq_file *m, void *arg)
1773 {
1774         kfree(m->private);
1775         m->private = NULL;
1776 }
1777
1778 struct seq_operations vmstat_op = {
1779         .start  = vmstat_start,
1780         .next   = vmstat_next,
1781         .stop   = vmstat_stop,
1782         .show   = vmstat_show,
1783 };
1784
1785 #endif /* CONFIG_PROC_FS */
1786
1787 #ifdef CONFIG_HOTPLUG_CPU
1788 static int page_alloc_cpu_notify(struct notifier_block *self,
1789                                  unsigned long action, void *hcpu)
1790 {
1791         int cpu = (unsigned long)hcpu;
1792         long *count;
1793
1794         if (action == CPU_DEAD) {
1795                 /* Drain local pagecache count. */
1796                 count = &per_cpu(nr_pagecache_local, cpu);
1797                 atomic_add(*count, &nr_pagecache);
1798                 *count = 0;
1799                 local_irq_disable();
1800                 __drain_pages(cpu);
1801                 local_irq_enable();
1802         }
1803         return NOTIFY_OK;
1804 }
1805 #endif /* CONFIG_HOTPLUG_CPU */
1806
1807 void __init page_alloc_init(void)
1808 {
1809         hotcpu_notifier(page_alloc_cpu_notify, 0);
1810 }
1811
1812 static unsigned long higherzone_val(struct zone *z, int max_zone,
1813                                         int alloc_type)
1814 {
1815         int z_idx = zone_idx(z);
1816         struct zone *higherzone;
1817         unsigned long pages;
1818
1819         /* there is no higher zone to get a contribution from */
1820         if (z_idx == MAX_NR_ZONES-1)
1821                 return 0;
1822
1823         higherzone = &z->zone_pgdat->node_zones[z_idx+1];
1824
1825         /* We always start with the higher zone's protection value */
1826         pages = higherzone->protection[alloc_type];
1827
1828         /*
1829          * We get a lower-zone-protection contribution only if there are
1830          * pages in the higher zone and if we're not the highest zone
1831          * in the current zonelist.  e.g., never happens for GFP_DMA. Happens
1832          * only for ZONE_DMA in a GFP_KERNEL allocation and happens for ZONE_DMA
1833          * and ZONE_NORMAL for a GFP_HIGHMEM allocation.
1834          */
1835         if (higherzone->present_pages && z_idx < alloc_type)
1836                 pages += higherzone->pages_low * sysctl_lower_zone_protection;
1837
1838         return pages;
1839 }
1840
1841 /*
1842  * setup_per_zone_protection - called whenver min_free_kbytes or
1843  *      sysctl_lower_zone_protection changes.  Ensures that each zone
1844  *      has a correct pages_protected value, so an adequate number of
1845  *      pages are left in the zone after a successful __alloc_pages().
1846  *
1847  *      This algorithm is way confusing.  I tries to keep the same behavior
1848  *      as we had with the incremental min iterative algorithm.
1849  */
1850 static void setup_per_zone_protection(void)
1851 {
1852         struct pglist_data *pgdat;
1853         struct zone *zones, *zone;
1854         int max_zone;
1855         int i, j;
1856
1857         for_each_pgdat(pgdat) {
1858                 zones = pgdat->node_zones;
1859
1860                 for (i = 0, max_zone = 0; i < MAX_NR_ZONES; i++)
1861                         if (zones[i].present_pages)
1862                                 max_zone = i;
1863
1864                 /*
1865                  * For each of the different allocation types:
1866                  * GFP_DMA -> GFP_KERNEL -> GFP_HIGHMEM
1867                  */
1868                 for (i = 0; i < MAX_NR_ZONES; i++) {
1869                         /*
1870                          * For each of the zones:
1871                          * ZONE_HIGHMEM -> ZONE_NORMAL -> ZONE_DMA
1872                          */
1873                         for (j = MAX_NR_ZONES-1; j >= 0; j--) {
1874                                 zone = &zones[j];
1875
1876                                 /*
1877                                  * We never protect zones that don't have memory
1878                                  * in them (j>max_zone) or zones that aren't in
1879                                  * the zonelists for a certain type of
1880                                  * allocation (j>i).  We have to assign these to
1881                                  * zero because the lower zones take
1882                                  * contributions from the higher zones.
1883                                  */
1884                                 if (j > max_zone || j > i) {
1885                                         zone->protection[i] = 0;
1886                                         continue;
1887                                 }
1888                                 /*
1889                                  * The contribution of the next higher zone
1890                                  */
1891                                 zone->protection[i] = higherzone_val(zone,
1892                                                                 max_zone, i);
1893                                 zone->protection[i] += zone->pages_low;
1894                         }
1895                 }
1896         }
1897 }
1898
1899 /*
1900  * setup_per_zone_pages_min - called when min_free_kbytes changes.  Ensures
1901  *      that the pages_{min,low,high} values for each zone are set correctly
1902  *      with respect to min_free_kbytes.
1903  */
1904 static void setup_per_zone_pages_min(void)
1905 {
1906         unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
1907         unsigned long lowmem_pages = 0;
1908         struct zone *zone;
1909         unsigned long flags;
1910
1911         /* Calculate total number of !ZONE_HIGHMEM pages */
1912         for_each_zone(zone) {
1913                 if (!is_highmem(zone))
1914                         lowmem_pages += zone->present_pages;
1915         }
1916
1917         for_each_zone(zone) {
1918                 spin_lock_irqsave(&zone->lru_lock, flags);
1919                 if (is_highmem(zone)) {
1920                         /*
1921                          * Often, highmem doesn't need to reserve any pages.
1922                          * But the pages_min/low/high values are also used for
1923                          * batching up page reclaim activity so we need a
1924                          * decent value here.
1925                          */
1926                         int min_pages;
1927
1928                         min_pages = zone->present_pages / 1024;
1929                         if (min_pages < SWAP_CLUSTER_MAX)
1930                                 min_pages = SWAP_CLUSTER_MAX;
1931                         if (min_pages > 128)
1932                                 min_pages = 128;
1933                         zone->pages_min = min_pages;
1934                 } else {
1935                         /* if it's a lowmem zone, reserve a number of pages
1936                          * proportionate to the zone's size.
1937                          */
1938                         zone->pages_min = (pages_min * zone->present_pages) /
1939                                            lowmem_pages;
1940                 }
1941
1942                 zone->pages_low = zone->pages_min * 2;
1943                 zone->pages_high = zone->pages_min * 3;
1944                 spin_unlock_irqrestore(&zone->lru_lock, flags);
1945         }
1946 }
1947
1948 /*
1949  * Initialise min_free_kbytes.
1950  *
1951  * For small machines we want it small (128k min).  For large machines
1952  * we want it large (16MB max).  But it is not linear, because network
1953  * bandwidth does not increase linearly with machine size.  We use
1954  *
1955  *      min_free_kbytes = sqrt(lowmem_kbytes)
1956  *
1957  * which yields
1958  *
1959  * 16MB:        128k
1960  * 32MB:        181k
1961  * 64MB:        256k
1962  * 128MB:       362k
1963  * 256MB:       512k
1964  * 512MB:       724k
1965  * 1024MB:      1024k
1966  * 2048MB:      1448k
1967  * 4096MB:      2048k
1968  * 8192MB:      2896k
1969  * 16384MB:     4096k
1970  */
1971 static int __init init_per_zone_pages_min(void)
1972 {
1973         unsigned long lowmem_kbytes;
1974
1975         lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
1976
1977         min_free_kbytes = int_sqrt(lowmem_kbytes);
1978         if (min_free_kbytes < 128)
1979                 min_free_kbytes = 128;
1980         if (min_free_kbytes > 16384)
1981                 min_free_kbytes = 16384;
1982         setup_per_zone_pages_min();
1983         setup_per_zone_protection();
1984         return 0;
1985 }
1986 module_init(init_per_zone_pages_min)
1987
1988 /*
1989  * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so
1990  *      that we can call two helper functions whenever min_free_kbytes
1991  *      changes.
1992  */
1993 int min_free_kbytes_sysctl_handler(ctl_table *table, int write,
1994                 struct file *file, void __user *buffer, size_t *length)
1995 {
1996         proc_dointvec(table, write, file, buffer, length);
1997         setup_per_zone_pages_min();
1998         setup_per_zone_protection();
1999         return 0;
2000 }
2001
2002 /*
2003  * lower_zone_protection_sysctl_handler - just a wrapper around
2004  *      proc_dointvec() so that we can call setup_per_zone_protection()
2005  *      whenever sysctl_lower_zone_protection changes.
2006  */
2007 int lower_zone_protection_sysctl_handler(ctl_table *table, int write,
2008                  struct file *file, void __user *buffer, size_t *length)
2009 {
2010         proc_dointvec_minmax(table, write, file, buffer, length);
2011         setup_per_zone_protection();
2012         return 0;
2013 }