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