mm/page_alloc.c

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