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