page_alloc.c revision 29751f6991e845f7d002a6ae520bf996b38c8dcd
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/cpuset.h> 35#include <linux/nodemask.h> 36#include <linux/vmalloc.h> 37 38#include <asm/tlbflush.h> 39#include "internal.h" 40 41/* 42 * MCD - HACK: Find somewhere to initialize this EARLY, or make this 43 * initializer cleaner 44 */ 45nodemask_t node_online_map = { { [0] = 1UL } }; 46EXPORT_SYMBOL(node_online_map); 47nodemask_t node_possible_map = NODE_MASK_ALL; 48EXPORT_SYMBOL(node_possible_map); 49struct pglist_data *pgdat_list; 50unsigned long totalram_pages; 51unsigned long totalhigh_pages; 52long nr_swap_pages; 53 54/* 55 * results with 256, 32 in the lowmem_reserve sysctl: 56 * 1G machine -> (16M dma, 800M-16M normal, 1G-800M high) 57 * 1G machine -> (16M dma, 784M normal, 224M high) 58 * NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA 59 * HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL 60 * HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA 61 */ 62int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { 256, 32 }; 63 64EXPORT_SYMBOL(totalram_pages); 65EXPORT_SYMBOL(nr_swap_pages); 66 67/* 68 * Used by page_zone() to look up the address of the struct zone whose 69 * id is encoded in the upper bits of page->flags 70 */ 71struct zone *zone_table[1 << ZONETABLE_SHIFT]; 72EXPORT_SYMBOL(zone_table); 73 74static char *zone_names[MAX_NR_ZONES] = { "DMA", "Normal", "HighMem" }; 75int min_free_kbytes = 1024; 76 77unsigned long __initdata nr_kernel_pages; 78unsigned long __initdata nr_all_pages; 79 80/* 81 * Temporary debugging check for pages not lying within a given zone. 82 */ 83static int bad_range(struct zone *zone, struct page *page) 84{ 85 if (page_to_pfn(page) >= zone->zone_start_pfn + zone->spanned_pages) 86 return 1; 87 if (page_to_pfn(page) < zone->zone_start_pfn) 88 return 1; 89#ifdef CONFIG_HOLES_IN_ZONE 90 if (!pfn_valid(page_to_pfn(page))) 91 return 1; 92#endif 93 if (zone != page_zone(page)) 94 return 1; 95 return 0; 96} 97 98static void bad_page(const char *function, struct page *page) 99{ 100 printk(KERN_EMERG "Bad page state at %s (in process '%s', page %p)\n", 101 function, current->comm, page); 102 printk(KERN_EMERG "flags:0x%0*lx mapping:%p mapcount:%d count:%d\n", 103 (int)(2*sizeof(page_flags_t)), (unsigned long)page->flags, 104 page->mapping, page_mapcount(page), page_count(page)); 105 printk(KERN_EMERG "Backtrace:\n"); 106 dump_stack(); 107 printk(KERN_EMERG "Trying to fix it up, but a reboot is needed\n"); 108 page->flags &= ~(1 << PG_lru | 109 1 << PG_private | 110 1 << PG_locked | 111 1 << PG_active | 112 1 << PG_dirty | 113 1 << PG_reclaim | 114 1 << PG_slab | 115 1 << PG_swapcache | 116 1 << PG_writeback); 117 set_page_count(page, 0); 118 reset_page_mapcount(page); 119 page->mapping = NULL; 120 tainted |= TAINT_BAD_PAGE; 121} 122 123#ifndef CONFIG_HUGETLB_PAGE 124#define prep_compound_page(page, order) do { } while (0) 125#define destroy_compound_page(page, order) do { } while (0) 126#else 127/* 128 * Higher-order pages are called "compound pages". They are structured thusly: 129 * 130 * The first PAGE_SIZE page is called the "head page". 131 * 132 * The remaining PAGE_SIZE pages are called "tail pages". 133 * 134 * All pages have PG_compound set. All pages have their ->private pointing at 135 * the head page (even the head page has this). 136 * 137 * The first tail page's ->mapping, if non-zero, holds the address of the 138 * compound page's put_page() function. 139 * 140 * The order of the allocation is stored in the first tail page's ->index 141 * This is only for debug at present. This usage means that zero-order pages 142 * may not be compound. 143 */ 144static void prep_compound_page(struct page *page, unsigned long order) 145{ 146 int i; 147 int nr_pages = 1 << order; 148 149 page[1].mapping = NULL; 150 page[1].index = order; 151 for (i = 0; i < nr_pages; i++) { 152 struct page *p = page + i; 153 154 SetPageCompound(p); 155 p->private = (unsigned long)page; 156 } 157} 158 159static void destroy_compound_page(struct page *page, unsigned long order) 160{ 161 int i; 162 int nr_pages = 1 << order; 163 164 if (!PageCompound(page)) 165 return; 166 167 if (page[1].index != order) 168 bad_page(__FUNCTION__, page); 169 170 for (i = 0; i < nr_pages; i++) { 171 struct page *p = page + i; 172 173 if (!PageCompound(p)) 174 bad_page(__FUNCTION__, page); 175 if (p->private != (unsigned long)page) 176 bad_page(__FUNCTION__, page); 177 ClearPageCompound(p); 178 } 179} 180#endif /* CONFIG_HUGETLB_PAGE */ 181 182/* 183 * function for dealing with page's order in buddy system. 184 * zone->lock is already acquired when we use these. 185 * So, we don't need atomic page->flags operations here. 186 */ 187static inline unsigned long page_order(struct page *page) { 188 return page->private; 189} 190 191static inline void set_page_order(struct page *page, int order) { 192 page->private = order; 193 __SetPagePrivate(page); 194} 195 196static inline void rmv_page_order(struct page *page) 197{ 198 __ClearPagePrivate(page); 199 page->private = 0; 200} 201 202/* 203 * Locate the struct page for both the matching buddy in our 204 * pair (buddy1) and the combined O(n+1) page they form (page). 205 * 206 * 1) Any buddy B1 will have an order O twin B2 which satisfies 207 * the following equation: 208 * B2 = B1 ^ (1 << O) 209 * For example, if the starting buddy (buddy2) is #8 its order 210 * 1 buddy is #10: 211 * B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10 212 * 213 * 2) Any buddy B will have an order O+1 parent P which 214 * satisfies the following equation: 215 * P = B & ~(1 << O) 216 * 217 * Assumption: *_mem_map is contigious at least up to MAX_ORDER 218 */ 219static inline struct page * 220__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order) 221{ 222 unsigned long buddy_idx = page_idx ^ (1 << order); 223 224 return page + (buddy_idx - page_idx); 225} 226 227static inline unsigned long 228__find_combined_index(unsigned long page_idx, unsigned int order) 229{ 230 return (page_idx & ~(1 << order)); 231} 232 233/* 234 * This function checks whether a page is free && is the buddy 235 * we can do coalesce a page and its buddy if 236 * (a) the buddy is free && 237 * (b) the buddy is on the buddy system && 238 * (c) a page and its buddy have the same order. 239 * for recording page's order, we use page->private and PG_private. 240 * 241 */ 242static inline int page_is_buddy(struct page *page, int order) 243{ 244 if (PagePrivate(page) && 245 (page_order(page) == order) && 246 !PageReserved(page) && 247 page_count(page) == 0) 248 return 1; 249 return 0; 250} 251 252/* 253 * Freeing function for a buddy system allocator. 254 * 255 * The concept of a buddy system is to maintain direct-mapped table 256 * (containing bit values) for memory blocks of various "orders". 257 * The bottom level table contains the map for the smallest allocatable 258 * units of memory (here, pages), and each level above it describes 259 * pairs of units from the levels below, hence, "buddies". 260 * At a high level, all that happens here is marking the table entry 261 * at the bottom level available, and propagating the changes upward 262 * as necessary, plus some accounting needed to play nicely with other 263 * parts of the VM system. 264 * At each level, we keep a list of pages, which are heads of continuous 265 * free pages of length of (1 << order) and marked with PG_Private.Page's 266 * order is recorded in page->private field. 267 * So when we are allocating or freeing one, we can derive the state of the 268 * other. That is, if we allocate a small block, and both were 269 * free, the remainder of the region must be split into blocks. 270 * If a block is freed, and its buddy is also free, then this 271 * triggers coalescing into a block of larger size. 272 * 273 * -- wli 274 */ 275 276static inline void __free_pages_bulk (struct page *page, 277 struct zone *zone, unsigned int order) 278{ 279 unsigned long page_idx; 280 int order_size = 1 << order; 281 282 if (unlikely(order)) 283 destroy_compound_page(page, order); 284 285 page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1); 286 287 BUG_ON(page_idx & (order_size - 1)); 288 BUG_ON(bad_range(zone, page)); 289 290 zone->free_pages += order_size; 291 while (order < MAX_ORDER-1) { 292 unsigned long combined_idx; 293 struct free_area *area; 294 struct page *buddy; 295 296 combined_idx = __find_combined_index(page_idx, order); 297 buddy = __page_find_buddy(page, page_idx, order); 298 299 if (bad_range(zone, buddy)) 300 break; 301 if (!page_is_buddy(buddy, order)) 302 break; /* Move the buddy up one level. */ 303 list_del(&buddy->lru); 304 area = zone->free_area + order; 305 area->nr_free--; 306 rmv_page_order(buddy); 307 page = page + (combined_idx - page_idx); 308 page_idx = combined_idx; 309 order++; 310 } 311 set_page_order(page, order); 312 list_add(&page->lru, &zone->free_area[order].free_list); 313 zone->free_area[order].nr_free++; 314} 315 316static inline void free_pages_check(const char *function, struct page *page) 317{ 318 if ( page_mapcount(page) || 319 page->mapping != NULL || 320 page_count(page) != 0 || 321 (page->flags & ( 322 1 << PG_lru | 323 1 << PG_private | 324 1 << PG_locked | 325 1 << PG_active | 326 1 << PG_reclaim | 327 1 << PG_slab | 328 1 << PG_swapcache | 329 1 << PG_writeback ))) 330 bad_page(function, page); 331 if (PageDirty(page)) 332 ClearPageDirty(page); 333} 334 335/* 336 * Frees a list of pages. 337 * Assumes all pages on list are in same zone, and of same order. 338 * count is the number of pages to free, or 0 for all on the list. 339 * 340 * If the zone was previously in an "all pages pinned" state then look to 341 * see if this freeing clears that state. 342 * 343 * And clear the zone's pages_scanned counter, to hold off the "all pages are 344 * pinned" detection logic. 345 */ 346static int 347free_pages_bulk(struct zone *zone, int count, 348 struct list_head *list, unsigned int order) 349{ 350 unsigned long flags; 351 struct page *page = NULL; 352 int ret = 0; 353 354 spin_lock_irqsave(&zone->lock, flags); 355 zone->all_unreclaimable = 0; 356 zone->pages_scanned = 0; 357 while (!list_empty(list) && count--) { 358 page = list_entry(list->prev, struct page, lru); 359 /* have to delete it as __free_pages_bulk list manipulates */ 360 list_del(&page->lru); 361 __free_pages_bulk(page, zone, order); 362 ret++; 363 } 364 spin_unlock_irqrestore(&zone->lock, flags); 365 return ret; 366} 367 368void __free_pages_ok(struct page *page, unsigned int order) 369{ 370 LIST_HEAD(list); 371 int i; 372 373 arch_free_page(page, order); 374 375 mod_page_state(pgfree, 1 << order); 376 377#ifndef CONFIG_MMU 378 if (order > 0) 379 for (i = 1 ; i < (1 << order) ; ++i) 380 __put_page(page + i); 381#endif 382 383 for (i = 0 ; i < (1 << order) ; ++i) 384 free_pages_check(__FUNCTION__, page + i); 385 list_add(&page->lru, &list); 386 kernel_map_pages(page, 1<<order, 0); 387 free_pages_bulk(page_zone(page), 1, &list, order); 388} 389 390 391/* 392 * The order of subdivision here is critical for the IO subsystem. 393 * Please do not alter this order without good reasons and regression 394 * testing. Specifically, as large blocks of memory are subdivided, 395 * the order in which smaller blocks are delivered depends on the order 396 * they're subdivided in this function. This is the primary factor 397 * influencing the order in which pages are delivered to the IO 398 * subsystem according to empirical testing, and this is also justified 399 * by considering the behavior of a buddy system containing a single 400 * large block of memory acted on by a series of small allocations. 401 * This behavior is a critical factor in sglist merging's success. 402 * 403 * -- wli 404 */ 405static inline struct page * 406expand(struct zone *zone, struct page *page, 407 int low, int high, struct free_area *area) 408{ 409 unsigned long size = 1 << high; 410 411 while (high > low) { 412 area--; 413 high--; 414 size >>= 1; 415 BUG_ON(bad_range(zone, &page[size])); 416 list_add(&page[size].lru, &area->free_list); 417 area->nr_free++; 418 set_page_order(&page[size], high); 419 } 420 return page; 421} 422 423void set_page_refs(struct page *page, int order) 424{ 425#ifdef CONFIG_MMU 426 set_page_count(page, 1); 427#else 428 int i; 429 430 /* 431 * We need to reference all the pages for this order, otherwise if 432 * anyone accesses one of the pages with (get/put) it will be freed. 433 * - eg: access_process_vm() 434 */ 435 for (i = 0; i < (1 << order); i++) 436 set_page_count(page + i, 1); 437#endif /* CONFIG_MMU */ 438} 439 440/* 441 * This page is about to be returned from the page allocator 442 */ 443static void prep_new_page(struct page *page, int order) 444{ 445 if ( page_mapcount(page) || 446 page->mapping != NULL || 447 page_count(page) != 0 || 448 (page->flags & ( 449 1 << PG_lru | 450 1 << PG_private | 451 1 << PG_locked | 452 1 << PG_active | 453 1 << PG_dirty | 454 1 << PG_reclaim | 455 1 << PG_slab | 456 1 << PG_swapcache | 457 1 << PG_writeback ))) 458 bad_page(__FUNCTION__, page); 459 460 page->flags &= ~(1 << PG_uptodate | 1 << PG_error | 461 1 << PG_referenced | 1 << PG_arch_1 | 462 1 << PG_checked | 1 << PG_mappedtodisk); 463 page->private = 0; 464 set_page_refs(page, order); 465 kernel_map_pages(page, 1 << order, 1); 466} 467 468/* 469 * Do the hard work of removing an element from the buddy allocator. 470 * Call me with the zone->lock already held. 471 */ 472static struct page *__rmqueue(struct zone *zone, unsigned int order) 473{ 474 struct free_area * area; 475 unsigned int current_order; 476 struct page *page; 477 478 for (current_order = order; current_order < MAX_ORDER; ++current_order) { 479 area = zone->free_area + current_order; 480 if (list_empty(&area->free_list)) 481 continue; 482 483 page = list_entry(area->free_list.next, struct page, lru); 484 list_del(&page->lru); 485 rmv_page_order(page); 486 area->nr_free--; 487 zone->free_pages -= 1UL << order; 488 return expand(zone, page, order, current_order, area); 489 } 490 491 return NULL; 492} 493 494/* 495 * Obtain a specified number of elements from the buddy allocator, all under 496 * a single hold of the lock, for efficiency. Add them to the supplied list. 497 * Returns the number of new pages which were placed at *list. 498 */ 499static int rmqueue_bulk(struct zone *zone, unsigned int order, 500 unsigned long count, struct list_head *list) 501{ 502 unsigned long flags; 503 int i; 504 int allocated = 0; 505 struct page *page; 506 507 spin_lock_irqsave(&zone->lock, flags); 508 for (i = 0; i < count; ++i) { 509 page = __rmqueue(zone, order); 510 if (page == NULL) 511 break; 512 allocated++; 513 list_add_tail(&page->lru, list); 514 } 515 spin_unlock_irqrestore(&zone->lock, flags); 516 return allocated; 517} 518 519#ifdef CONFIG_NUMA 520/* Called from the slab reaper to drain remote pagesets */ 521void drain_remote_pages(void) 522{ 523 struct zone *zone; 524 int i; 525 unsigned long flags; 526 527 local_irq_save(flags); 528 for_each_zone(zone) { 529 struct per_cpu_pageset *pset; 530 531 /* Do not drain local pagesets */ 532 if (zone->zone_pgdat->node_id == numa_node_id()) 533 continue; 534 535 pset = zone->pageset[smp_processor_id()]; 536 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) { 537 struct per_cpu_pages *pcp; 538 539 pcp = &pset->pcp[i]; 540 if (pcp->count) 541 pcp->count -= free_pages_bulk(zone, pcp->count, 542 &pcp->list, 0); 543 } 544 } 545 local_irq_restore(flags); 546} 547#endif 548 549#if defined(CONFIG_PM) || defined(CONFIG_HOTPLUG_CPU) 550static void __drain_pages(unsigned int cpu) 551{ 552 struct zone *zone; 553 int i; 554 555 for_each_zone(zone) { 556 struct per_cpu_pageset *pset; 557 558 pset = zone_pcp(zone, cpu); 559 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) { 560 struct per_cpu_pages *pcp; 561 562 pcp = &pset->pcp[i]; 563 pcp->count -= free_pages_bulk(zone, pcp->count, 564 &pcp->list, 0); 565 } 566 } 567} 568#endif /* CONFIG_PM || CONFIG_HOTPLUG_CPU */ 569 570#ifdef CONFIG_PM 571 572void mark_free_pages(struct zone *zone) 573{ 574 unsigned long zone_pfn, flags; 575 int order; 576 struct list_head *curr; 577 578 if (!zone->spanned_pages) 579 return; 580 581 spin_lock_irqsave(&zone->lock, flags); 582 for (zone_pfn = 0; zone_pfn < zone->spanned_pages; ++zone_pfn) 583 ClearPageNosaveFree(pfn_to_page(zone_pfn + zone->zone_start_pfn)); 584 585 for (order = MAX_ORDER - 1; order >= 0; --order) 586 list_for_each(curr, &zone->free_area[order].free_list) { 587 unsigned long start_pfn, i; 588 589 start_pfn = page_to_pfn(list_entry(curr, struct page, lru)); 590 591 for (i=0; i < (1<<order); i++) 592 SetPageNosaveFree(pfn_to_page(start_pfn+i)); 593 } 594 spin_unlock_irqrestore(&zone->lock, flags); 595} 596 597/* 598 * Spill all of this CPU's per-cpu pages back into the buddy allocator. 599 */ 600void drain_local_pages(void) 601{ 602 unsigned long flags; 603 604 local_irq_save(flags); 605 __drain_pages(smp_processor_id()); 606 local_irq_restore(flags); 607} 608#endif /* CONFIG_PM */ 609 610static void zone_statistics(struct zonelist *zonelist, struct zone *z) 611{ 612#ifdef CONFIG_NUMA 613 unsigned long flags; 614 int cpu; 615 pg_data_t *pg = z->zone_pgdat; 616 pg_data_t *orig = zonelist->zones[0]->zone_pgdat; 617 struct per_cpu_pageset *p; 618 619 local_irq_save(flags); 620 cpu = smp_processor_id(); 621 p = zone_pcp(z,cpu); 622 if (pg == orig) { 623 p->numa_hit++; 624 } else { 625 p->numa_miss++; 626 zone_pcp(zonelist->zones[0], cpu)->numa_foreign++; 627 } 628 if (pg == NODE_DATA(numa_node_id())) 629 p->local_node++; 630 else 631 p->other_node++; 632 local_irq_restore(flags); 633#endif 634} 635 636/* 637 * Free a 0-order page 638 */ 639static void FASTCALL(free_hot_cold_page(struct page *page, int cold)); 640static void fastcall free_hot_cold_page(struct page *page, int cold) 641{ 642 struct zone *zone = page_zone(page); 643 struct per_cpu_pages *pcp; 644 unsigned long flags; 645 646 arch_free_page(page, 0); 647 648 kernel_map_pages(page, 1, 0); 649 inc_page_state(pgfree); 650 if (PageAnon(page)) 651 page->mapping = NULL; 652 free_pages_check(__FUNCTION__, page); 653 pcp = &zone_pcp(zone, get_cpu())->pcp[cold]; 654 local_irq_save(flags); 655 list_add(&page->lru, &pcp->list); 656 pcp->count++; 657 if (pcp->count >= pcp->high) 658 pcp->count -= free_pages_bulk(zone, pcp->batch, &pcp->list, 0); 659 local_irq_restore(flags); 660 put_cpu(); 661} 662 663void fastcall free_hot_page(struct page *page) 664{ 665 free_hot_cold_page(page, 0); 666} 667 668void fastcall free_cold_page(struct page *page) 669{ 670 free_hot_cold_page(page, 1); 671} 672 673static inline void prep_zero_page(struct page *page, int order, unsigned int __nocast gfp_flags) 674{ 675 int i; 676 677 BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM); 678 for(i = 0; i < (1 << order); i++) 679 clear_highpage(page + i); 680} 681 682/* 683 * Really, prep_compound_page() should be called from __rmqueue_bulk(). But 684 * we cheat by calling it from here, in the order > 0 path. Saves a branch 685 * or two. 686 */ 687static struct page * 688buffered_rmqueue(struct zone *zone, int order, unsigned int __nocast gfp_flags) 689{ 690 unsigned long flags; 691 struct page *page = NULL; 692 int cold = !!(gfp_flags & __GFP_COLD); 693 694 if (order == 0) { 695 struct per_cpu_pages *pcp; 696 697 pcp = &zone_pcp(zone, get_cpu())->pcp[cold]; 698 local_irq_save(flags); 699 if (pcp->count <= pcp->low) 700 pcp->count += rmqueue_bulk(zone, 0, 701 pcp->batch, &pcp->list); 702 if (pcp->count) { 703 page = list_entry(pcp->list.next, struct page, lru); 704 list_del(&page->lru); 705 pcp->count--; 706 } 707 local_irq_restore(flags); 708 put_cpu(); 709 } 710 711 if (page == NULL) { 712 spin_lock_irqsave(&zone->lock, flags); 713 page = __rmqueue(zone, order); 714 spin_unlock_irqrestore(&zone->lock, flags); 715 } 716 717 if (page != NULL) { 718 BUG_ON(bad_range(zone, page)); 719 mod_page_state_zone(zone, pgalloc, 1 << order); 720 prep_new_page(page, order); 721 722 if (gfp_flags & __GFP_ZERO) 723 prep_zero_page(page, order, gfp_flags); 724 725 if (order && (gfp_flags & __GFP_COMP)) 726 prep_compound_page(page, order); 727 } 728 return page; 729} 730 731/* 732 * Return 1 if free pages are above 'mark'. This takes into account the order 733 * of the allocation. 734 */ 735int zone_watermark_ok(struct zone *z, int order, unsigned long mark, 736 int classzone_idx, int can_try_harder, int gfp_high) 737{ 738 /* free_pages my go negative - that's OK */ 739 long min = mark, free_pages = z->free_pages - (1 << order) + 1; 740 int o; 741 742 if (gfp_high) 743 min -= min / 2; 744 if (can_try_harder) 745 min -= min / 4; 746 747 if (free_pages <= min + z->lowmem_reserve[classzone_idx]) 748 return 0; 749 for (o = 0; o < order; o++) { 750 /* At the next order, this order's pages become unavailable */ 751 free_pages -= z->free_area[o].nr_free << o; 752 753 /* Require fewer higher order pages to be free */ 754 min >>= 1; 755 756 if (free_pages <= min) 757 return 0; 758 } 759 return 1; 760} 761 762static inline int 763should_reclaim_zone(struct zone *z, unsigned int gfp_mask) 764{ 765 if (!z->reclaim_pages) 766 return 0; 767 if (gfp_mask & __GFP_NORECLAIM) 768 return 0; 769 return 1; 770} 771 772/* 773 * This is the 'heart' of the zoned buddy allocator. 774 */ 775struct page * fastcall 776__alloc_pages(unsigned int __nocast gfp_mask, unsigned int order, 777 struct zonelist *zonelist) 778{ 779 const int wait = gfp_mask & __GFP_WAIT; 780 struct zone **zones, *z; 781 struct page *page; 782 struct reclaim_state reclaim_state; 783 struct task_struct *p = current; 784 int i; 785 int classzone_idx; 786 int do_retry; 787 int can_try_harder; 788 int did_some_progress; 789 790 might_sleep_if(wait); 791 792 /* 793 * The caller may dip into page reserves a bit more if the caller 794 * cannot run direct reclaim, or is the caller has realtime scheduling 795 * policy 796 */ 797 can_try_harder = (unlikely(rt_task(p)) && !in_interrupt()) || !wait; 798 799 zones = zonelist->zones; /* the list of zones suitable for gfp_mask */ 800 801 if (unlikely(zones[0] == NULL)) { 802 /* Should this ever happen?? */ 803 return NULL; 804 } 805 806 classzone_idx = zone_idx(zones[0]); 807 808restart: 809 /* Go through the zonelist once, looking for a zone with enough free */ 810 for (i = 0; (z = zones[i]) != NULL; i++) { 811 int do_reclaim = should_reclaim_zone(z, gfp_mask); 812 813 if (!cpuset_zone_allowed(z)) 814 continue; 815 816 /* 817 * If the zone is to attempt early page reclaim then this loop 818 * will try to reclaim pages and check the watermark a second 819 * time before giving up and falling back to the next zone. 820 */ 821zone_reclaim_retry: 822 if (!zone_watermark_ok(z, order, z->pages_low, 823 classzone_idx, 0, 0)) { 824 if (!do_reclaim) 825 continue; 826 else { 827 zone_reclaim(z, gfp_mask, order); 828 /* Only try reclaim once */ 829 do_reclaim = 0; 830 goto zone_reclaim_retry; 831 } 832 } 833 834 page = buffered_rmqueue(z, order, gfp_mask); 835 if (page) 836 goto got_pg; 837 } 838 839 for (i = 0; (z = zones[i]) != NULL; i++) 840 wakeup_kswapd(z, order); 841 842 /* 843 * Go through the zonelist again. Let __GFP_HIGH and allocations 844 * coming from realtime tasks to go deeper into reserves 845 * 846 * This is the last chance, in general, before the goto nopage. 847 * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc. 848 */ 849 for (i = 0; (z = zones[i]) != NULL; i++) { 850 if (!zone_watermark_ok(z, order, z->pages_min, 851 classzone_idx, can_try_harder, 852 gfp_mask & __GFP_HIGH)) 853 continue; 854 855 if (wait && !cpuset_zone_allowed(z)) 856 continue; 857 858 page = buffered_rmqueue(z, order, gfp_mask); 859 if (page) 860 goto got_pg; 861 } 862 863 /* This allocation should allow future memory freeing. */ 864 865 if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE))) 866 && !in_interrupt()) { 867 if (!(gfp_mask & __GFP_NOMEMALLOC)) { 868 /* go through the zonelist yet again, ignoring mins */ 869 for (i = 0; (z = zones[i]) != NULL; i++) { 870 if (!cpuset_zone_allowed(z)) 871 continue; 872 page = buffered_rmqueue(z, order, gfp_mask); 873 if (page) 874 goto got_pg; 875 } 876 } 877 goto nopage; 878 } 879 880 /* Atomic allocations - we can't balance anything */ 881 if (!wait) 882 goto nopage; 883 884rebalance: 885 cond_resched(); 886 887 /* We now go into synchronous reclaim */ 888 p->flags |= PF_MEMALLOC; 889 reclaim_state.reclaimed_slab = 0; 890 p->reclaim_state = &reclaim_state; 891 892 did_some_progress = try_to_free_pages(zones, gfp_mask); 893 894 p->reclaim_state = NULL; 895 p->flags &= ~PF_MEMALLOC; 896 897 cond_resched(); 898 899 if (likely(did_some_progress)) { 900 /* 901 * Go through the zonelist yet one more time, keep 902 * very high watermark here, this is only to catch 903 * a parallel oom killing, we must fail if we're still 904 * under heavy pressure. 905 */ 906 for (i = 0; (z = zones[i]) != NULL; i++) { 907 if (!zone_watermark_ok(z, order, z->pages_min, 908 classzone_idx, can_try_harder, 909 gfp_mask & __GFP_HIGH)) 910 continue; 911 912 if (!cpuset_zone_allowed(z)) 913 continue; 914 915 page = buffered_rmqueue(z, order, gfp_mask); 916 if (page) 917 goto got_pg; 918 } 919 } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) { 920 /* 921 * Go through the zonelist yet one more time, keep 922 * very high watermark here, this is only to catch 923 * a parallel oom killing, we must fail if we're still 924 * under heavy pressure. 925 */ 926 for (i = 0; (z = zones[i]) != NULL; i++) { 927 if (!zone_watermark_ok(z, order, z->pages_high, 928 classzone_idx, 0, 0)) 929 continue; 930 931 if (!cpuset_zone_allowed(z)) 932 continue; 933 934 page = buffered_rmqueue(z, order, gfp_mask); 935 if (page) 936 goto got_pg; 937 } 938 939 out_of_memory(gfp_mask); 940 goto restart; 941 } 942 943 /* 944 * Don't let big-order allocations loop unless the caller explicitly 945 * requests that. Wait for some write requests to complete then retry. 946 * 947 * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order 948 * <= 3, but that may not be true in other implementations. 949 */ 950 do_retry = 0; 951 if (!(gfp_mask & __GFP_NORETRY)) { 952 if ((order <= 3) || (gfp_mask & __GFP_REPEAT)) 953 do_retry = 1; 954 if (gfp_mask & __GFP_NOFAIL) 955 do_retry = 1; 956 } 957 if (do_retry) { 958 blk_congestion_wait(WRITE, HZ/50); 959 goto rebalance; 960 } 961 962nopage: 963 if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) { 964 printk(KERN_WARNING "%s: page allocation failure." 965 " order:%d, mode:0x%x\n", 966 p->comm, order, gfp_mask); 967 dump_stack(); 968 show_mem(); 969 } 970 return NULL; 971got_pg: 972 zone_statistics(zonelist, z); 973 return page; 974} 975 976EXPORT_SYMBOL(__alloc_pages); 977 978/* 979 * Common helper functions. 980 */ 981fastcall unsigned long __get_free_pages(unsigned int __nocast gfp_mask, unsigned int order) 982{ 983 struct page * page; 984 page = alloc_pages(gfp_mask, order); 985 if (!page) 986 return 0; 987 return (unsigned long) page_address(page); 988} 989 990EXPORT_SYMBOL(__get_free_pages); 991 992fastcall unsigned long get_zeroed_page(unsigned int __nocast gfp_mask) 993{ 994 struct page * page; 995 996 /* 997 * get_zeroed_page() returns a 32-bit address, which cannot represent 998 * a highmem page 999 */ 1000 BUG_ON(gfp_mask & __GFP_HIGHMEM); 1001 1002 page = alloc_pages(gfp_mask | __GFP_ZERO, 0); 1003 if (page) 1004 return (unsigned long) page_address(page); 1005 return 0; 1006} 1007 1008EXPORT_SYMBOL(get_zeroed_page); 1009 1010void __pagevec_free(struct pagevec *pvec) 1011{ 1012 int i = pagevec_count(pvec); 1013 1014 while (--i >= 0) 1015 free_hot_cold_page(pvec->pages[i], pvec->cold); 1016} 1017 1018fastcall void __free_pages(struct page *page, unsigned int order) 1019{ 1020 if (!PageReserved(page) && put_page_testzero(page)) { 1021 if (order == 0) 1022 free_hot_page(page); 1023 else 1024 __free_pages_ok(page, order); 1025 } 1026} 1027 1028EXPORT_SYMBOL(__free_pages); 1029 1030fastcall void free_pages(unsigned long addr, unsigned int order) 1031{ 1032 if (addr != 0) { 1033 BUG_ON(!virt_addr_valid((void *)addr)); 1034 __free_pages(virt_to_page((void *)addr), order); 1035 } 1036} 1037 1038EXPORT_SYMBOL(free_pages); 1039 1040/* 1041 * Total amount of free (allocatable) RAM: 1042 */ 1043unsigned int nr_free_pages(void) 1044{ 1045 unsigned int sum = 0; 1046 struct zone *zone; 1047 1048 for_each_zone(zone) 1049 sum += zone->free_pages; 1050 1051 return sum; 1052} 1053 1054EXPORT_SYMBOL(nr_free_pages); 1055 1056#ifdef CONFIG_NUMA 1057unsigned int nr_free_pages_pgdat(pg_data_t *pgdat) 1058{ 1059 unsigned int i, sum = 0; 1060 1061 for (i = 0; i < MAX_NR_ZONES; i++) 1062 sum += pgdat->node_zones[i].free_pages; 1063 1064 return sum; 1065} 1066#endif 1067 1068static unsigned int nr_free_zone_pages(int offset) 1069{ 1070 pg_data_t *pgdat; 1071 unsigned int sum = 0; 1072 1073 for_each_pgdat(pgdat) { 1074 struct zonelist *zonelist = pgdat->node_zonelists + offset; 1075 struct zone **zonep = zonelist->zones; 1076 struct zone *zone; 1077 1078 for (zone = *zonep++; zone; zone = *zonep++) { 1079 unsigned long size = zone->present_pages; 1080 unsigned long high = zone->pages_high; 1081 if (size > high) 1082 sum += size - high; 1083 } 1084 } 1085 1086 return sum; 1087} 1088 1089/* 1090 * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL 1091 */ 1092unsigned int nr_free_buffer_pages(void) 1093{ 1094 return nr_free_zone_pages(GFP_USER & GFP_ZONEMASK); 1095} 1096 1097/* 1098 * Amount of free RAM allocatable within all zones 1099 */ 1100unsigned int nr_free_pagecache_pages(void) 1101{ 1102 return nr_free_zone_pages(GFP_HIGHUSER & GFP_ZONEMASK); 1103} 1104 1105#ifdef CONFIG_HIGHMEM 1106unsigned int nr_free_highpages (void) 1107{ 1108 pg_data_t *pgdat; 1109 unsigned int pages = 0; 1110 1111 for_each_pgdat(pgdat) 1112 pages += pgdat->node_zones[ZONE_HIGHMEM].free_pages; 1113 1114 return pages; 1115} 1116#endif 1117 1118#ifdef CONFIG_NUMA 1119static void show_node(struct zone *zone) 1120{ 1121 printk("Node %d ", zone->zone_pgdat->node_id); 1122} 1123#else 1124#define show_node(zone) do { } while (0) 1125#endif 1126 1127/* 1128 * Accumulate the page_state information across all CPUs. 1129 * The result is unavoidably approximate - it can change 1130 * during and after execution of this function. 1131 */ 1132static DEFINE_PER_CPU(struct page_state, page_states) = {0}; 1133 1134atomic_t nr_pagecache = ATOMIC_INIT(0); 1135EXPORT_SYMBOL(nr_pagecache); 1136#ifdef CONFIG_SMP 1137DEFINE_PER_CPU(long, nr_pagecache_local) = 0; 1138#endif 1139 1140void __get_page_state(struct page_state *ret, int nr) 1141{ 1142 int cpu = 0; 1143 1144 memset(ret, 0, sizeof(*ret)); 1145 1146 cpu = first_cpu(cpu_online_map); 1147 while (cpu < NR_CPUS) { 1148 unsigned long *in, *out, off; 1149 1150 in = (unsigned long *)&per_cpu(page_states, cpu); 1151 1152 cpu = next_cpu(cpu, cpu_online_map); 1153 1154 if (cpu < NR_CPUS) 1155 prefetch(&per_cpu(page_states, cpu)); 1156 1157 out = (unsigned long *)ret; 1158 for (off = 0; off < nr; off++) 1159 *out++ += *in++; 1160 } 1161} 1162 1163void get_page_state(struct page_state *ret) 1164{ 1165 int nr; 1166 1167 nr = offsetof(struct page_state, GET_PAGE_STATE_LAST); 1168 nr /= sizeof(unsigned long); 1169 1170 __get_page_state(ret, nr + 1); 1171} 1172 1173void get_full_page_state(struct page_state *ret) 1174{ 1175 __get_page_state(ret, sizeof(*ret) / sizeof(unsigned long)); 1176} 1177 1178unsigned long __read_page_state(unsigned long offset) 1179{ 1180 unsigned long ret = 0; 1181 int cpu; 1182 1183 for_each_online_cpu(cpu) { 1184 unsigned long in; 1185 1186 in = (unsigned long)&per_cpu(page_states, cpu) + offset; 1187 ret += *((unsigned long *)in); 1188 } 1189 return ret; 1190} 1191 1192void __mod_page_state(unsigned long offset, unsigned long delta) 1193{ 1194 unsigned long flags; 1195 void* ptr; 1196 1197 local_irq_save(flags); 1198 ptr = &__get_cpu_var(page_states); 1199 *(unsigned long*)(ptr + offset) += delta; 1200 local_irq_restore(flags); 1201} 1202 1203EXPORT_SYMBOL(__mod_page_state); 1204 1205void __get_zone_counts(unsigned long *active, unsigned long *inactive, 1206 unsigned long *free, struct pglist_data *pgdat) 1207{ 1208 struct zone *zones = pgdat->node_zones; 1209 int i; 1210 1211 *active = 0; 1212 *inactive = 0; 1213 *free = 0; 1214 for (i = 0; i < MAX_NR_ZONES; i++) { 1215 *active += zones[i].nr_active; 1216 *inactive += zones[i].nr_inactive; 1217 *free += zones[i].free_pages; 1218 } 1219} 1220 1221void get_zone_counts(unsigned long *active, 1222 unsigned long *inactive, unsigned long *free) 1223{ 1224 struct pglist_data *pgdat; 1225 1226 *active = 0; 1227 *inactive = 0; 1228 *free = 0; 1229 for_each_pgdat(pgdat) { 1230 unsigned long l, m, n; 1231 __get_zone_counts(&l, &m, &n, pgdat); 1232 *active += l; 1233 *inactive += m; 1234 *free += n; 1235 } 1236} 1237 1238void si_meminfo(struct sysinfo *val) 1239{ 1240 val->totalram = totalram_pages; 1241 val->sharedram = 0; 1242 val->freeram = nr_free_pages(); 1243 val->bufferram = nr_blockdev_pages(); 1244#ifdef CONFIG_HIGHMEM 1245 val->totalhigh = totalhigh_pages; 1246 val->freehigh = nr_free_highpages(); 1247#else 1248 val->totalhigh = 0; 1249 val->freehigh = 0; 1250#endif 1251 val->mem_unit = PAGE_SIZE; 1252} 1253 1254EXPORT_SYMBOL(si_meminfo); 1255 1256#ifdef CONFIG_NUMA 1257void si_meminfo_node(struct sysinfo *val, int nid) 1258{ 1259 pg_data_t *pgdat = NODE_DATA(nid); 1260 1261 val->totalram = pgdat->node_present_pages; 1262 val->freeram = nr_free_pages_pgdat(pgdat); 1263 val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages; 1264 val->freehigh = pgdat->node_zones[ZONE_HIGHMEM].free_pages; 1265 val->mem_unit = PAGE_SIZE; 1266} 1267#endif 1268 1269#define K(x) ((x) << (PAGE_SHIFT-10)) 1270 1271/* 1272 * Show free area list (used inside shift_scroll-lock stuff) 1273 * We also calculate the percentage fragmentation. We do this by counting the 1274 * memory on each free list with the exception of the first item on the list. 1275 */ 1276void show_free_areas(void) 1277{ 1278 struct page_state ps; 1279 int cpu, temperature; 1280 unsigned long active; 1281 unsigned long inactive; 1282 unsigned long free; 1283 struct zone *zone; 1284 1285 for_each_zone(zone) { 1286 show_node(zone); 1287 printk("%s per-cpu:", zone->name); 1288 1289 if (!zone->present_pages) { 1290 printk(" empty\n"); 1291 continue; 1292 } else 1293 printk("\n"); 1294 1295 for (cpu = 0; cpu < NR_CPUS; ++cpu) { 1296 struct per_cpu_pageset *pageset; 1297 1298 if (!cpu_possible(cpu)) 1299 continue; 1300 1301 pageset = zone_pcp(zone, cpu); 1302 1303 for (temperature = 0; temperature < 2; temperature++) 1304 printk("cpu %d %s: low %d, high %d, batch %d used:%d\n", 1305 cpu, 1306 temperature ? "cold" : "hot", 1307 pageset->pcp[temperature].low, 1308 pageset->pcp[temperature].high, 1309 pageset->pcp[temperature].batch, 1310 pageset->pcp[temperature].count); 1311 } 1312 } 1313 1314 get_page_state(&ps); 1315 get_zone_counts(&active, &inactive, &free); 1316 1317 printk("Free pages: %11ukB (%ukB HighMem)\n", 1318 K(nr_free_pages()), 1319 K(nr_free_highpages())); 1320 1321 printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu " 1322 "unstable:%lu free:%u slab:%lu mapped:%lu pagetables:%lu\n", 1323 active, 1324 inactive, 1325 ps.nr_dirty, 1326 ps.nr_writeback, 1327 ps.nr_unstable, 1328 nr_free_pages(), 1329 ps.nr_slab, 1330 ps.nr_mapped, 1331 ps.nr_page_table_pages); 1332 1333 for_each_zone(zone) { 1334 int i; 1335 1336 show_node(zone); 1337 printk("%s" 1338 " free:%lukB" 1339 " min:%lukB" 1340 " low:%lukB" 1341 " high:%lukB" 1342 " active:%lukB" 1343 " inactive:%lukB" 1344 " present:%lukB" 1345 " pages_scanned:%lu" 1346 " all_unreclaimable? %s" 1347 "\n", 1348 zone->name, 1349 K(zone->free_pages), 1350 K(zone->pages_min), 1351 K(zone->pages_low), 1352 K(zone->pages_high), 1353 K(zone->nr_active), 1354 K(zone->nr_inactive), 1355 K(zone->present_pages), 1356 zone->pages_scanned, 1357 (zone->all_unreclaimable ? "yes" : "no") 1358 ); 1359 printk("lowmem_reserve[]:"); 1360 for (i = 0; i < MAX_NR_ZONES; i++) 1361 printk(" %lu", zone->lowmem_reserve[i]); 1362 printk("\n"); 1363 } 1364 1365 for_each_zone(zone) { 1366 unsigned long nr, flags, order, total = 0; 1367 1368 show_node(zone); 1369 printk("%s: ", zone->name); 1370 if (!zone->present_pages) { 1371 printk("empty\n"); 1372 continue; 1373 } 1374 1375 spin_lock_irqsave(&zone->lock, flags); 1376 for (order = 0; order < MAX_ORDER; order++) { 1377 nr = zone->free_area[order].nr_free; 1378 total += nr << order; 1379 printk("%lu*%lukB ", nr, K(1UL) << order); 1380 } 1381 spin_unlock_irqrestore(&zone->lock, flags); 1382 printk("= %lukB\n", K(total)); 1383 } 1384 1385 show_swap_cache_info(); 1386} 1387 1388/* 1389 * Builds allocation fallback zone lists. 1390 */ 1391static int __init build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist, int j, int k) 1392{ 1393 switch (k) { 1394 struct zone *zone; 1395 default: 1396 BUG(); 1397 case ZONE_HIGHMEM: 1398 zone = pgdat->node_zones + ZONE_HIGHMEM; 1399 if (zone->present_pages) { 1400#ifndef CONFIG_HIGHMEM 1401 BUG(); 1402#endif 1403 zonelist->zones[j++] = zone; 1404 } 1405 case ZONE_NORMAL: 1406 zone = pgdat->node_zones + ZONE_NORMAL; 1407 if (zone->present_pages) 1408 zonelist->zones[j++] = zone; 1409 case ZONE_DMA: 1410 zone = pgdat->node_zones + ZONE_DMA; 1411 if (zone->present_pages) 1412 zonelist->zones[j++] = zone; 1413 } 1414 1415 return j; 1416} 1417 1418#ifdef CONFIG_NUMA 1419#define MAX_NODE_LOAD (num_online_nodes()) 1420static int __initdata node_load[MAX_NUMNODES]; 1421/** 1422 * find_next_best_node - find the next node that should appear in a given node's fallback list 1423 * @node: node whose fallback list we're appending 1424 * @used_node_mask: nodemask_t of already used nodes 1425 * 1426 * We use a number of factors to determine which is the next node that should 1427 * appear on a given node's fallback list. The node should not have appeared 1428 * already in @node's fallback list, and it should be the next closest node 1429 * according to the distance array (which contains arbitrary distance values 1430 * from each node to each node in the system), and should also prefer nodes 1431 * with no CPUs, since presumably they'll have very little allocation pressure 1432 * on them otherwise. 1433 * It returns -1 if no node is found. 1434 */ 1435static int __init find_next_best_node(int node, nodemask_t *used_node_mask) 1436{ 1437 int i, n, val; 1438 int min_val = INT_MAX; 1439 int best_node = -1; 1440 1441 for_each_online_node(i) { 1442 cpumask_t tmp; 1443 1444 /* Start from local node */ 1445 n = (node+i) % num_online_nodes(); 1446 1447 /* Don't want a node to appear more than once */ 1448 if (node_isset(n, *used_node_mask)) 1449 continue; 1450 1451 /* Use the local node if we haven't already */ 1452 if (!node_isset(node, *used_node_mask)) { 1453 best_node = node; 1454 break; 1455 } 1456 1457 /* Use the distance array to find the distance */ 1458 val = node_distance(node, n); 1459 1460 /* Give preference to headless and unused nodes */ 1461 tmp = node_to_cpumask(n); 1462 if (!cpus_empty(tmp)) 1463 val += PENALTY_FOR_NODE_WITH_CPUS; 1464 1465 /* Slight preference for less loaded node */ 1466 val *= (MAX_NODE_LOAD*MAX_NUMNODES); 1467 val += node_load[n]; 1468 1469 if (val < min_val) { 1470 min_val = val; 1471 best_node = n; 1472 } 1473 } 1474 1475 if (best_node >= 0) 1476 node_set(best_node, *used_node_mask); 1477 1478 return best_node; 1479} 1480 1481static void __init build_zonelists(pg_data_t *pgdat) 1482{ 1483 int i, j, k, node, local_node; 1484 int prev_node, load; 1485 struct zonelist *zonelist; 1486 nodemask_t used_mask; 1487 1488 /* initialize zonelists */ 1489 for (i = 0; i < GFP_ZONETYPES; i++) { 1490 zonelist = pgdat->node_zonelists + i; 1491 zonelist->zones[0] = NULL; 1492 } 1493 1494 /* NUMA-aware ordering of nodes */ 1495 local_node = pgdat->node_id; 1496 load = num_online_nodes(); 1497 prev_node = local_node; 1498 nodes_clear(used_mask); 1499 while ((node = find_next_best_node(local_node, &used_mask)) >= 0) { 1500 /* 1501 * We don't want to pressure a particular node. 1502 * So adding penalty to the first node in same 1503 * distance group to make it round-robin. 1504 */ 1505 if (node_distance(local_node, node) != 1506 node_distance(local_node, prev_node)) 1507 node_load[node] += load; 1508 prev_node = node; 1509 load--; 1510 for (i = 0; i < GFP_ZONETYPES; i++) { 1511 zonelist = pgdat->node_zonelists + i; 1512 for (j = 0; zonelist->zones[j] != NULL; j++); 1513 1514 k = ZONE_NORMAL; 1515 if (i & __GFP_HIGHMEM) 1516 k = ZONE_HIGHMEM; 1517 if (i & __GFP_DMA) 1518 k = ZONE_DMA; 1519 1520 j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); 1521 zonelist->zones[j] = NULL; 1522 } 1523 } 1524} 1525 1526#else /* CONFIG_NUMA */ 1527 1528static void __init build_zonelists(pg_data_t *pgdat) 1529{ 1530 int i, j, k, node, local_node; 1531 1532 local_node = pgdat->node_id; 1533 for (i = 0; i < GFP_ZONETYPES; i++) { 1534 struct zonelist *zonelist; 1535 1536 zonelist = pgdat->node_zonelists + i; 1537 1538 j = 0; 1539 k = ZONE_NORMAL; 1540 if (i & __GFP_HIGHMEM) 1541 k = ZONE_HIGHMEM; 1542 if (i & __GFP_DMA) 1543 k = ZONE_DMA; 1544 1545 j = build_zonelists_node(pgdat, zonelist, j, k); 1546 /* 1547 * Now we build the zonelist so that it contains the zones 1548 * of all the other nodes. 1549 * We don't want to pressure a particular node, so when 1550 * building the zones for node N, we make sure that the 1551 * zones coming right after the local ones are those from 1552 * node N+1 (modulo N) 1553 */ 1554 for (node = local_node + 1; node < MAX_NUMNODES; node++) { 1555 if (!node_online(node)) 1556 continue; 1557 j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); 1558 } 1559 for (node = 0; node < local_node; node++) { 1560 if (!node_online(node)) 1561 continue; 1562 j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); 1563 } 1564 1565 zonelist->zones[j] = NULL; 1566 } 1567} 1568 1569#endif /* CONFIG_NUMA */ 1570 1571void __init build_all_zonelists(void) 1572{ 1573 int i; 1574 1575 for_each_online_node(i) 1576 build_zonelists(NODE_DATA(i)); 1577 printk("Built %i zonelists\n", num_online_nodes()); 1578 cpuset_init_current_mems_allowed(); 1579} 1580 1581/* 1582 * Helper functions to size the waitqueue hash table. 1583 * Essentially these want to choose hash table sizes sufficiently 1584 * large so that collisions trying to wait on pages are rare. 1585 * But in fact, the number of active page waitqueues on typical 1586 * systems is ridiculously low, less than 200. So this is even 1587 * conservative, even though it seems large. 1588 * 1589 * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to 1590 * waitqueues, i.e. the size of the waitq table given the number of pages. 1591 */ 1592#define PAGES_PER_WAITQUEUE 256 1593 1594static inline unsigned long wait_table_size(unsigned long pages) 1595{ 1596 unsigned long size = 1; 1597 1598 pages /= PAGES_PER_WAITQUEUE; 1599 1600 while (size < pages) 1601 size <<= 1; 1602 1603 /* 1604 * Once we have dozens or even hundreds of threads sleeping 1605 * on IO we've got bigger problems than wait queue collision. 1606 * Limit the size of the wait table to a reasonable size. 1607 */ 1608 size = min(size, 4096UL); 1609 1610 return max(size, 4UL); 1611} 1612 1613/* 1614 * This is an integer logarithm so that shifts can be used later 1615 * to extract the more random high bits from the multiplicative 1616 * hash function before the remainder is taken. 1617 */ 1618static inline unsigned long wait_table_bits(unsigned long size) 1619{ 1620 return ffz(~size); 1621} 1622 1623#define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1)) 1624 1625static void __init calculate_zone_totalpages(struct pglist_data *pgdat, 1626 unsigned long *zones_size, unsigned long *zholes_size) 1627{ 1628 unsigned long realtotalpages, totalpages = 0; 1629 int i; 1630 1631 for (i = 0; i < MAX_NR_ZONES; i++) 1632 totalpages += zones_size[i]; 1633 pgdat->node_spanned_pages = totalpages; 1634 1635 realtotalpages = totalpages; 1636 if (zholes_size) 1637 for (i = 0; i < MAX_NR_ZONES; i++) 1638 realtotalpages -= zholes_size[i]; 1639 pgdat->node_present_pages = realtotalpages; 1640 printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id, realtotalpages); 1641} 1642 1643 1644/* 1645 * Initially all pages are reserved - free ones are freed 1646 * up by free_all_bootmem() once the early boot process is 1647 * done. Non-atomic initialization, single-pass. 1648 */ 1649void __init memmap_init_zone(unsigned long size, int nid, unsigned long zone, 1650 unsigned long start_pfn) 1651{ 1652 struct page *page; 1653 unsigned long end_pfn = start_pfn + size; 1654 unsigned long pfn; 1655 1656 for (pfn = start_pfn; pfn < end_pfn; pfn++, page++) { 1657 if (!early_pfn_valid(pfn)) 1658 continue; 1659 if (!early_pfn_in_nid(pfn, nid)) 1660 continue; 1661 page = pfn_to_page(pfn); 1662 set_page_links(page, zone, nid, pfn); 1663 set_page_count(page, 0); 1664 reset_page_mapcount(page); 1665 SetPageReserved(page); 1666 INIT_LIST_HEAD(&page->lru); 1667#ifdef WANT_PAGE_VIRTUAL 1668 /* The shift won't overflow because ZONE_NORMAL is below 4G. */ 1669 if (!is_highmem_idx(zone)) 1670 set_page_address(page, __va(start_pfn << PAGE_SHIFT)); 1671#endif 1672 start_pfn++; 1673 } 1674} 1675 1676void zone_init_free_lists(struct pglist_data *pgdat, struct zone *zone, 1677 unsigned long size) 1678{ 1679 int order; 1680 for (order = 0; order < MAX_ORDER ; order++) { 1681 INIT_LIST_HEAD(&zone->free_area[order].free_list); 1682 zone->free_area[order].nr_free = 0; 1683 } 1684} 1685 1686#define ZONETABLE_INDEX(x, zone_nr) ((x << ZONES_SHIFT) | zone_nr) 1687void zonetable_add(struct zone *zone, int nid, int zid, unsigned long pfn, 1688 unsigned long size) 1689{ 1690 unsigned long snum = pfn_to_section_nr(pfn); 1691 unsigned long end = pfn_to_section_nr(pfn + size); 1692 1693 if (FLAGS_HAS_NODE) 1694 zone_table[ZONETABLE_INDEX(nid, zid)] = zone; 1695 else 1696 for (; snum <= end; snum++) 1697 zone_table[ZONETABLE_INDEX(snum, zid)] = zone; 1698} 1699 1700#ifndef __HAVE_ARCH_MEMMAP_INIT 1701#define memmap_init(size, nid, zone, start_pfn) \ 1702 memmap_init_zone((size), (nid), (zone), (start_pfn)) 1703#endif 1704 1705static int __devinit zone_batchsize(struct zone *zone) 1706{ 1707 int batch; 1708 1709 /* 1710 * The per-cpu-pages pools are set to around 1000th of the 1711 * size of the zone. But no more than 1/4 of a meg - there's 1712 * no point in going beyond the size of L2 cache. 1713 * 1714 * OK, so we don't know how big the cache is. So guess. 1715 */ 1716 batch = zone->present_pages / 1024; 1717 if (batch * PAGE_SIZE > 256 * 1024) 1718 batch = (256 * 1024) / PAGE_SIZE; 1719 batch /= 4; /* We effectively *= 4 below */ 1720 if (batch < 1) 1721 batch = 1; 1722 1723 /* 1724 * Clamp the batch to a 2^n - 1 value. Having a power 1725 * of 2 value was found to be more likely to have 1726 * suboptimal cache aliasing properties in some cases. 1727 * 1728 * For example if 2 tasks are alternately allocating 1729 * batches of pages, one task can end up with a lot 1730 * of pages of one half of the possible page colors 1731 * and the other with pages of the other colors. 1732 */ 1733 batch = (1 << fls(batch + batch/2)) - 1; 1734 return batch; 1735} 1736 1737inline void setup_pageset(struct per_cpu_pageset *p, unsigned long batch) 1738{ 1739 struct per_cpu_pages *pcp; 1740 1741 pcp = &p->pcp[0]; /* hot */ 1742 pcp->count = 0; 1743 pcp->low = 2 * batch; 1744 pcp->high = 6 * batch; 1745 pcp->batch = max(1UL, 1 * batch); 1746 INIT_LIST_HEAD(&pcp->list); 1747 1748 pcp = &p->pcp[1]; /* cold*/ 1749 pcp->count = 0; 1750 pcp->low = 0; 1751 pcp->high = 2 * batch; 1752 pcp->batch = max(1UL, 1 * batch); 1753 INIT_LIST_HEAD(&pcp->list); 1754} 1755 1756#ifdef CONFIG_NUMA 1757/* 1758 * Boot pageset table. One per cpu which is going to be used for all 1759 * zones and all nodes. The parameters will be set in such a way 1760 * that an item put on a list will immediately be handed over to 1761 * the buddy list. This is safe since pageset manipulation is done 1762 * with interrupts disabled. 1763 * 1764 * Some NUMA counter updates may also be caught by the boot pagesets. 1765 * 1766 * The boot_pagesets must be kept even after bootup is complete for 1767 * unused processors and/or zones. They do play a role for bootstrapping 1768 * hotplugged processors. 1769 * 1770 * zoneinfo_show() and maybe other functions do 1771 * not check if the processor is online before following the pageset pointer. 1772 * Other parts of the kernel may not check if the zone is available. 1773 */ 1774static struct per_cpu_pageset 1775 boot_pageset[NR_CPUS]; 1776 1777/* 1778 * Dynamically allocate memory for the 1779 * per cpu pageset array in struct zone. 1780 */ 1781static int __devinit process_zones(int cpu) 1782{ 1783 struct zone *zone, *dzone; 1784 1785 for_each_zone(zone) { 1786 1787 zone->pageset[cpu] = kmalloc_node(sizeof(struct per_cpu_pageset), 1788 GFP_KERNEL, cpu_to_node(cpu)); 1789 if (!zone->pageset[cpu]) 1790 goto bad; 1791 1792 setup_pageset(zone->pageset[cpu], zone_batchsize(zone)); 1793 } 1794 1795 return 0; 1796bad: 1797 for_each_zone(dzone) { 1798 if (dzone == zone) 1799 break; 1800 kfree(dzone->pageset[cpu]); 1801 dzone->pageset[cpu] = NULL; 1802 } 1803 return -ENOMEM; 1804} 1805 1806static inline void free_zone_pagesets(int cpu) 1807{ 1808#ifdef CONFIG_NUMA 1809 struct zone *zone; 1810 1811 for_each_zone(zone) { 1812 struct per_cpu_pageset *pset = zone_pcp(zone, cpu); 1813 1814 zone_pcp(zone, cpu) = NULL; 1815 kfree(pset); 1816 } 1817#endif 1818} 1819 1820static int __devinit pageset_cpuup_callback(struct notifier_block *nfb, 1821 unsigned long action, 1822 void *hcpu) 1823{ 1824 int cpu = (long)hcpu; 1825 int ret = NOTIFY_OK; 1826 1827 switch (action) { 1828 case CPU_UP_PREPARE: 1829 if (process_zones(cpu)) 1830 ret = NOTIFY_BAD; 1831 break; 1832#ifdef CONFIG_HOTPLUG_CPU 1833 case CPU_DEAD: 1834 free_zone_pagesets(cpu); 1835 break; 1836#endif 1837 default: 1838 break; 1839 } 1840 return ret; 1841} 1842 1843static struct notifier_block pageset_notifier = 1844 { &pageset_cpuup_callback, NULL, 0 }; 1845 1846void __init setup_per_cpu_pageset() 1847{ 1848 int err; 1849 1850 /* Initialize per_cpu_pageset for cpu 0. 1851 * A cpuup callback will do this for every cpu 1852 * as it comes online 1853 */ 1854 err = process_zones(smp_processor_id()); 1855 BUG_ON(err); 1856 register_cpu_notifier(&pageset_notifier); 1857} 1858 1859#endif 1860 1861/* 1862 * Set up the zone data structures: 1863 * - mark all pages reserved 1864 * - mark all memory queues empty 1865 * - clear the memory bitmaps 1866 */ 1867static void __init free_area_init_core(struct pglist_data *pgdat, 1868 unsigned long *zones_size, unsigned long *zholes_size) 1869{ 1870 unsigned long i, j; 1871 const unsigned long zone_required_alignment = 1UL << (MAX_ORDER-1); 1872 int cpu, nid = pgdat->node_id; 1873 unsigned long zone_start_pfn = pgdat->node_start_pfn; 1874 1875 pgdat->nr_zones = 0; 1876 init_waitqueue_head(&pgdat->kswapd_wait); 1877 pgdat->kswapd_max_order = 0; 1878 1879 for (j = 0; j < MAX_NR_ZONES; j++) { 1880 struct zone *zone = pgdat->node_zones + j; 1881 unsigned long size, realsize; 1882 unsigned long batch; 1883 1884 realsize = size = zones_size[j]; 1885 if (zholes_size) 1886 realsize -= zholes_size[j]; 1887 1888 if (j == ZONE_DMA || j == ZONE_NORMAL) 1889 nr_kernel_pages += realsize; 1890 nr_all_pages += realsize; 1891 1892 zone->spanned_pages = size; 1893 zone->present_pages = realsize; 1894 zone->name = zone_names[j]; 1895 spin_lock_init(&zone->lock); 1896 spin_lock_init(&zone->lru_lock); 1897 zone->zone_pgdat = pgdat; 1898 zone->free_pages = 0; 1899 1900 zone->temp_priority = zone->prev_priority = DEF_PRIORITY; 1901 1902 batch = zone_batchsize(zone); 1903 1904 for (cpu = 0; cpu < NR_CPUS; cpu++) { 1905#ifdef CONFIG_NUMA 1906 /* Early boot. Slab allocator not functional yet */ 1907 zone->pageset[cpu] = &boot_pageset[cpu]; 1908 setup_pageset(&boot_pageset[cpu],0); 1909#else 1910 setup_pageset(zone_pcp(zone,cpu), batch); 1911#endif 1912 } 1913 printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lu\n", 1914 zone_names[j], realsize, batch); 1915 INIT_LIST_HEAD(&zone->active_list); 1916 INIT_LIST_HEAD(&zone->inactive_list); 1917 zone->nr_scan_active = 0; 1918 zone->nr_scan_inactive = 0; 1919 zone->nr_active = 0; 1920 zone->nr_inactive = 0; 1921 atomic_set(&zone->reclaim_in_progress, -1); 1922 if (!size) 1923 continue; 1924 1925 /* 1926 * The per-page waitqueue mechanism uses hashed waitqueues 1927 * per zone. 1928 */ 1929 zone->wait_table_size = wait_table_size(size); 1930 zone->wait_table_bits = 1931 wait_table_bits(zone->wait_table_size); 1932 zone->wait_table = (wait_queue_head_t *) 1933 alloc_bootmem_node(pgdat, zone->wait_table_size 1934 * sizeof(wait_queue_head_t)); 1935 1936 for(i = 0; i < zone->wait_table_size; ++i) 1937 init_waitqueue_head(zone->wait_table + i); 1938 1939 pgdat->nr_zones = j+1; 1940 1941 zone->zone_mem_map = pfn_to_page(zone_start_pfn); 1942 zone->zone_start_pfn = zone_start_pfn; 1943 1944 if ((zone_start_pfn) & (zone_required_alignment-1)) 1945 printk(KERN_CRIT "BUG: wrong zone alignment, it will crash\n"); 1946 1947 memmap_init(size, nid, j, zone_start_pfn); 1948 1949 zonetable_add(zone, nid, j, zone_start_pfn, size); 1950 1951 zone_start_pfn += size; 1952 1953 zone_init_free_lists(pgdat, zone, zone->spanned_pages); 1954 } 1955} 1956 1957static void __init alloc_node_mem_map(struct pglist_data *pgdat) 1958{ 1959 /* Skip empty nodes */ 1960 if (!pgdat->node_spanned_pages) 1961 return; 1962 1963#ifdef CONFIG_FLAT_NODE_MEM_MAP 1964 /* ia64 gets its own node_mem_map, before this, without bootmem */ 1965 if (!pgdat->node_mem_map) { 1966 unsigned long size; 1967 struct page *map; 1968 1969 size = (pgdat->node_spanned_pages + 1) * sizeof(struct page); 1970 map = alloc_remap(pgdat->node_id, size); 1971 if (!map) 1972 map = alloc_bootmem_node(pgdat, size); 1973 pgdat->node_mem_map = map; 1974 } 1975#ifdef CONFIG_FLATMEM 1976 /* 1977 * With no DISCONTIG, the global mem_map is just set as node 0's 1978 */ 1979 if (pgdat == NODE_DATA(0)) 1980 mem_map = NODE_DATA(0)->node_mem_map; 1981#endif 1982#endif /* CONFIG_FLAT_NODE_MEM_MAP */ 1983} 1984 1985void __init free_area_init_node(int nid, struct pglist_data *pgdat, 1986 unsigned long *zones_size, unsigned long node_start_pfn, 1987 unsigned long *zholes_size) 1988{ 1989 pgdat->node_id = nid; 1990 pgdat->node_start_pfn = node_start_pfn; 1991 calculate_zone_totalpages(pgdat, zones_size, zholes_size); 1992 1993 alloc_node_mem_map(pgdat); 1994 1995 free_area_init_core(pgdat, zones_size, zholes_size); 1996} 1997 1998#ifndef CONFIG_NEED_MULTIPLE_NODES 1999static bootmem_data_t contig_bootmem_data; 2000struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data }; 2001 2002EXPORT_SYMBOL(contig_page_data); 2003#endif 2004 2005void __init free_area_init(unsigned long *zones_size) 2006{ 2007 free_area_init_node(0, NODE_DATA(0), zones_size, 2008 __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL); 2009} 2010 2011#ifdef CONFIG_PROC_FS 2012 2013#include <linux/seq_file.h> 2014 2015static void *frag_start(struct seq_file *m, loff_t *pos) 2016{ 2017 pg_data_t *pgdat; 2018 loff_t node = *pos; 2019 2020 for (pgdat = pgdat_list; pgdat && node; pgdat = pgdat->pgdat_next) 2021 --node; 2022 2023 return pgdat; 2024} 2025 2026static void *frag_next(struct seq_file *m, void *arg, loff_t *pos) 2027{ 2028 pg_data_t *pgdat = (pg_data_t *)arg; 2029 2030 (*pos)++; 2031 return pgdat->pgdat_next; 2032} 2033 2034static void frag_stop(struct seq_file *m, void *arg) 2035{ 2036} 2037 2038/* 2039 * This walks the free areas for each zone. 2040 */ 2041static int frag_show(struct seq_file *m, void *arg) 2042{ 2043 pg_data_t *pgdat = (pg_data_t *)arg; 2044 struct zone *zone; 2045 struct zone *node_zones = pgdat->node_zones; 2046 unsigned long flags; 2047 int order; 2048 2049 for (zone = node_zones; zone - node_zones < MAX_NR_ZONES; ++zone) { 2050 if (!zone->present_pages) 2051 continue; 2052 2053 spin_lock_irqsave(&zone->lock, flags); 2054 seq_printf(m, "Node %d, zone %8s ", pgdat->node_id, zone->name); 2055 for (order = 0; order < MAX_ORDER; ++order) 2056 seq_printf(m, "%6lu ", zone->free_area[order].nr_free); 2057 spin_unlock_irqrestore(&zone->lock, flags); 2058 seq_putc(m, '\n'); 2059 } 2060 return 0; 2061} 2062 2063struct seq_operations fragmentation_op = { 2064 .start = frag_start, 2065 .next = frag_next, 2066 .stop = frag_stop, 2067 .show = frag_show, 2068}; 2069 2070/* 2071 * Output information about zones in @pgdat. 2072 */ 2073static int zoneinfo_show(struct seq_file *m, void *arg) 2074{ 2075 pg_data_t *pgdat = arg; 2076 struct zone *zone; 2077 struct zone *node_zones = pgdat->node_zones; 2078 unsigned long flags; 2079 2080 for (zone = node_zones; zone - node_zones < MAX_NR_ZONES; zone++) { 2081 int i; 2082 2083 if (!zone->present_pages) 2084 continue; 2085 2086 spin_lock_irqsave(&zone->lock, flags); 2087 seq_printf(m, "Node %d, zone %8s", pgdat->node_id, zone->name); 2088 seq_printf(m, 2089 "\n pages free %lu" 2090 "\n min %lu" 2091 "\n low %lu" 2092 "\n high %lu" 2093 "\n active %lu" 2094 "\n inactive %lu" 2095 "\n scanned %lu (a: %lu i: %lu)" 2096 "\n spanned %lu" 2097 "\n present %lu", 2098 zone->free_pages, 2099 zone->pages_min, 2100 zone->pages_low, 2101 zone->pages_high, 2102 zone->nr_active, 2103 zone->nr_inactive, 2104 zone->pages_scanned, 2105 zone->nr_scan_active, zone->nr_scan_inactive, 2106 zone->spanned_pages, 2107 zone->present_pages); 2108 seq_printf(m, 2109 "\n protection: (%lu", 2110 zone->lowmem_reserve[0]); 2111 for (i = 1; i < ARRAY_SIZE(zone->lowmem_reserve); i++) 2112 seq_printf(m, ", %lu", zone->lowmem_reserve[i]); 2113 seq_printf(m, 2114 ")" 2115 "\n pagesets"); 2116 for (i = 0; i < ARRAY_SIZE(zone->pageset); i++) { 2117 struct per_cpu_pageset *pageset; 2118 int j; 2119 2120 pageset = zone_pcp(zone, i); 2121 for (j = 0; j < ARRAY_SIZE(pageset->pcp); j++) { 2122 if (pageset->pcp[j].count) 2123 break; 2124 } 2125 if (j == ARRAY_SIZE(pageset->pcp)) 2126 continue; 2127 for (j = 0; j < ARRAY_SIZE(pageset->pcp); j++) { 2128 seq_printf(m, 2129 "\n cpu: %i pcp: %i" 2130 "\n count: %i" 2131 "\n low: %i" 2132 "\n high: %i" 2133 "\n batch: %i", 2134 i, j, 2135 pageset->pcp[j].count, 2136 pageset->pcp[j].low, 2137 pageset->pcp[j].high, 2138 pageset->pcp[j].batch); 2139 } 2140#ifdef CONFIG_NUMA 2141 seq_printf(m, 2142 "\n numa_hit: %lu" 2143 "\n numa_miss: %lu" 2144 "\n numa_foreign: %lu" 2145 "\n interleave_hit: %lu" 2146 "\n local_node: %lu" 2147 "\n other_node: %lu", 2148 pageset->numa_hit, 2149 pageset->numa_miss, 2150 pageset->numa_foreign, 2151 pageset->interleave_hit, 2152 pageset->local_node, 2153 pageset->other_node); 2154#endif 2155 } 2156 seq_printf(m, 2157 "\n all_unreclaimable: %u" 2158 "\n prev_priority: %i" 2159 "\n temp_priority: %i" 2160 "\n start_pfn: %lu", 2161 zone->all_unreclaimable, 2162 zone->prev_priority, 2163 zone->temp_priority, 2164 zone->zone_start_pfn); 2165 spin_unlock_irqrestore(&zone->lock, flags); 2166 seq_putc(m, '\n'); 2167 } 2168 return 0; 2169} 2170 2171struct seq_operations zoneinfo_op = { 2172 .start = frag_start, /* iterate over all zones. The same as in 2173 * fragmentation. */ 2174 .next = frag_next, 2175 .stop = frag_stop, 2176 .show = zoneinfo_show, 2177}; 2178 2179static char *vmstat_text[] = { 2180 "nr_dirty", 2181 "nr_writeback", 2182 "nr_unstable", 2183 "nr_page_table_pages", 2184 "nr_mapped", 2185 "nr_slab", 2186 2187 "pgpgin", 2188 "pgpgout", 2189 "pswpin", 2190 "pswpout", 2191 "pgalloc_high", 2192 2193 "pgalloc_normal", 2194 "pgalloc_dma", 2195 "pgfree", 2196 "pgactivate", 2197 "pgdeactivate", 2198 2199 "pgfault", 2200 "pgmajfault", 2201 "pgrefill_high", 2202 "pgrefill_normal", 2203 "pgrefill_dma", 2204 2205 "pgsteal_high", 2206 "pgsteal_normal", 2207 "pgsteal_dma", 2208 "pgscan_kswapd_high", 2209 "pgscan_kswapd_normal", 2210 2211 "pgscan_kswapd_dma", 2212 "pgscan_direct_high", 2213 "pgscan_direct_normal", 2214 "pgscan_direct_dma", 2215 "pginodesteal", 2216 2217 "slabs_scanned", 2218 "kswapd_steal", 2219 "kswapd_inodesteal", 2220 "pageoutrun", 2221 "allocstall", 2222 2223 "pgrotated", 2224 "nr_bounce", 2225}; 2226 2227static void *vmstat_start(struct seq_file *m, loff_t *pos) 2228{ 2229 struct page_state *ps; 2230 2231 if (*pos >= ARRAY_SIZE(vmstat_text)) 2232 return NULL; 2233 2234 ps = kmalloc(sizeof(*ps), GFP_KERNEL); 2235 m->private = ps; 2236 if (!ps) 2237 return ERR_PTR(-ENOMEM); 2238 get_full_page_state(ps); 2239 ps->pgpgin /= 2; /* sectors -> kbytes */ 2240 ps->pgpgout /= 2; 2241 return (unsigned long *)ps + *pos; 2242} 2243 2244static void *vmstat_next(struct seq_file *m, void *arg, loff_t *pos) 2245{ 2246 (*pos)++; 2247 if (*pos >= ARRAY_SIZE(vmstat_text)) 2248 return NULL; 2249 return (unsigned long *)m->private + *pos; 2250} 2251 2252static int vmstat_show(struct seq_file *m, void *arg) 2253{ 2254 unsigned long *l = arg; 2255 unsigned long off = l - (unsigned long *)m->private; 2256 2257 seq_printf(m, "%s %lu\n", vmstat_text[off], *l); 2258 return 0; 2259} 2260 2261static void vmstat_stop(struct seq_file *m, void *arg) 2262{ 2263 kfree(m->private); 2264 m->private = NULL; 2265} 2266 2267struct seq_operations vmstat_op = { 2268 .start = vmstat_start, 2269 .next = vmstat_next, 2270 .stop = vmstat_stop, 2271 .show = vmstat_show, 2272}; 2273 2274#endif /* CONFIG_PROC_FS */ 2275 2276#ifdef CONFIG_HOTPLUG_CPU 2277static int page_alloc_cpu_notify(struct notifier_block *self, 2278 unsigned long action, void *hcpu) 2279{ 2280 int cpu = (unsigned long)hcpu; 2281 long *count; 2282 unsigned long *src, *dest; 2283 2284 if (action == CPU_DEAD) { 2285 int i; 2286 2287 /* Drain local pagecache count. */ 2288 count = &per_cpu(nr_pagecache_local, cpu); 2289 atomic_add(*count, &nr_pagecache); 2290 *count = 0; 2291 local_irq_disable(); 2292 __drain_pages(cpu); 2293 2294 /* Add dead cpu's page_states to our own. */ 2295 dest = (unsigned long *)&__get_cpu_var(page_states); 2296 src = (unsigned long *)&per_cpu(page_states, cpu); 2297 2298 for (i = 0; i < sizeof(struct page_state)/sizeof(unsigned long); 2299 i++) { 2300 dest[i] += src[i]; 2301 src[i] = 0; 2302 } 2303 2304 local_irq_enable(); 2305 } 2306 return NOTIFY_OK; 2307} 2308#endif /* CONFIG_HOTPLUG_CPU */ 2309 2310void __init page_alloc_init(void) 2311{ 2312 hotcpu_notifier(page_alloc_cpu_notify, 0); 2313} 2314 2315/* 2316 * setup_per_zone_lowmem_reserve - called whenever 2317 * sysctl_lower_zone_reserve_ratio changes. Ensures that each zone 2318 * has a correct pages reserved value, so an adequate number of 2319 * pages are left in the zone after a successful __alloc_pages(). 2320 */ 2321static void setup_per_zone_lowmem_reserve(void) 2322{ 2323 struct pglist_data *pgdat; 2324 int j, idx; 2325 2326 for_each_pgdat(pgdat) { 2327 for (j = 0; j < MAX_NR_ZONES; j++) { 2328 struct zone *zone = pgdat->node_zones + j; 2329 unsigned long present_pages = zone->present_pages; 2330 2331 zone->lowmem_reserve[j] = 0; 2332 2333 for (idx = j-1; idx >= 0; idx--) { 2334 struct zone *lower_zone; 2335 2336 if (sysctl_lowmem_reserve_ratio[idx] < 1) 2337 sysctl_lowmem_reserve_ratio[idx] = 1; 2338 2339 lower_zone = pgdat->node_zones + idx; 2340 lower_zone->lowmem_reserve[j] = present_pages / 2341 sysctl_lowmem_reserve_ratio[idx]; 2342 present_pages += lower_zone->present_pages; 2343 } 2344 } 2345 } 2346} 2347 2348/* 2349 * setup_per_zone_pages_min - called when min_free_kbytes changes. Ensures 2350 * that the pages_{min,low,high} values for each zone are set correctly 2351 * with respect to min_free_kbytes. 2352 */ 2353static void setup_per_zone_pages_min(void) 2354{ 2355 unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10); 2356 unsigned long lowmem_pages = 0; 2357 struct zone *zone; 2358 unsigned long flags; 2359 2360 /* Calculate total number of !ZONE_HIGHMEM pages */ 2361 for_each_zone(zone) { 2362 if (!is_highmem(zone)) 2363 lowmem_pages += zone->present_pages; 2364 } 2365 2366 for_each_zone(zone) { 2367 spin_lock_irqsave(&zone->lru_lock, flags); 2368 if (is_highmem(zone)) { 2369 /* 2370 * Often, highmem doesn't need to reserve any pages. 2371 * But the pages_min/low/high values are also used for 2372 * batching up page reclaim activity so we need a 2373 * decent value here. 2374 */ 2375 int min_pages; 2376 2377 min_pages = zone->present_pages / 1024; 2378 if (min_pages < SWAP_CLUSTER_MAX) 2379 min_pages = SWAP_CLUSTER_MAX; 2380 if (min_pages > 128) 2381 min_pages = 128; 2382 zone->pages_min = min_pages; 2383 } else { 2384 /* if it's a lowmem zone, reserve a number of pages 2385 * proportionate to the zone's size. 2386 */ 2387 zone->pages_min = (pages_min * zone->present_pages) / 2388 lowmem_pages; 2389 } 2390 2391 /* 2392 * When interpreting these watermarks, just keep in mind that: 2393 * zone->pages_min == (zone->pages_min * 4) / 4; 2394 */ 2395 zone->pages_low = (zone->pages_min * 5) / 4; 2396 zone->pages_high = (zone->pages_min * 6) / 4; 2397 spin_unlock_irqrestore(&zone->lru_lock, flags); 2398 } 2399} 2400 2401/* 2402 * Initialise min_free_kbytes. 2403 * 2404 * For small machines we want it small (128k min). For large machines 2405 * we want it large (64MB max). But it is not linear, because network 2406 * bandwidth does not increase linearly with machine size. We use 2407 * 2408 * min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy: 2409 * min_free_kbytes = sqrt(lowmem_kbytes * 16) 2410 * 2411 * which yields 2412 * 2413 * 16MB: 512k 2414 * 32MB: 724k 2415 * 64MB: 1024k 2416 * 128MB: 1448k 2417 * 256MB: 2048k 2418 * 512MB: 2896k 2419 * 1024MB: 4096k 2420 * 2048MB: 5792k 2421 * 4096MB: 8192k 2422 * 8192MB: 11584k 2423 * 16384MB: 16384k 2424 */ 2425static int __init init_per_zone_pages_min(void) 2426{ 2427 unsigned long lowmem_kbytes; 2428 2429 lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10); 2430 2431 min_free_kbytes = int_sqrt(lowmem_kbytes * 16); 2432 if (min_free_kbytes < 128) 2433 min_free_kbytes = 128; 2434 if (min_free_kbytes > 65536) 2435 min_free_kbytes = 65536; 2436 setup_per_zone_pages_min(); 2437 setup_per_zone_lowmem_reserve(); 2438 return 0; 2439} 2440module_init(init_per_zone_pages_min) 2441 2442/* 2443 * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so 2444 * that we can call two helper functions whenever min_free_kbytes 2445 * changes. 2446 */ 2447int min_free_kbytes_sysctl_handler(ctl_table *table, int write, 2448 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 2449{ 2450 proc_dointvec(table, write, file, buffer, length, ppos); 2451 setup_per_zone_pages_min(); 2452 return 0; 2453} 2454 2455/* 2456 * lowmem_reserve_ratio_sysctl_handler - just a wrapper around 2457 * proc_dointvec() so that we can call setup_per_zone_lowmem_reserve() 2458 * whenever sysctl_lowmem_reserve_ratio changes. 2459 * 2460 * The reserve ratio obviously has absolutely no relation with the 2461 * pages_min watermarks. The lowmem reserve ratio can only make sense 2462 * if in function of the boot time zone sizes. 2463 */ 2464int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write, 2465 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 2466{ 2467 proc_dointvec_minmax(table, write, file, buffer, length, ppos); 2468 setup_per_zone_lowmem_reserve(); 2469 return 0; 2470} 2471 2472__initdata int hashdist = HASHDIST_DEFAULT; 2473 2474#ifdef CONFIG_NUMA 2475static int __init set_hashdist(char *str) 2476{ 2477 if (!str) 2478 return 0; 2479 hashdist = simple_strtoul(str, &str, 0); 2480 return 1; 2481} 2482__setup("hashdist=", set_hashdist); 2483#endif 2484 2485/* 2486 * allocate a large system hash table from bootmem 2487 * - it is assumed that the hash table must contain an exact power-of-2 2488 * quantity of entries 2489 * - limit is the number of hash buckets, not the total allocation size 2490 */ 2491void *__init alloc_large_system_hash(const char *tablename, 2492 unsigned long bucketsize, 2493 unsigned long numentries, 2494 int scale, 2495 int flags, 2496 unsigned int *_hash_shift, 2497 unsigned int *_hash_mask, 2498 unsigned long limit) 2499{ 2500 unsigned long long max = limit; 2501 unsigned long log2qty, size; 2502 void *table = NULL; 2503 2504 /* allow the kernel cmdline to have a say */ 2505 if (!numentries) { 2506 /* round applicable memory size up to nearest megabyte */ 2507 numentries = (flags & HASH_HIGHMEM) ? nr_all_pages : nr_kernel_pages; 2508 numentries += (1UL << (20 - PAGE_SHIFT)) - 1; 2509 numentries >>= 20 - PAGE_SHIFT; 2510 numentries <<= 20 - PAGE_SHIFT; 2511 2512 /* limit to 1 bucket per 2^scale bytes of low memory */ 2513 if (scale > PAGE_SHIFT) 2514 numentries >>= (scale - PAGE_SHIFT); 2515 else 2516 numentries <<= (PAGE_SHIFT - scale); 2517 } 2518 /* rounded up to nearest power of 2 in size */ 2519 numentries = 1UL << (long_log2(numentries) + 1); 2520 2521 /* limit allocation size to 1/16 total memory by default */ 2522 if (max == 0) { 2523 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4; 2524 do_div(max, bucketsize); 2525 } 2526 2527 if (numentries > max) 2528 numentries = max; 2529 2530 log2qty = long_log2(numentries); 2531 2532 do { 2533 size = bucketsize << log2qty; 2534 if (flags & HASH_EARLY) 2535 table = alloc_bootmem(size); 2536 else if (hashdist) 2537 table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL); 2538 else { 2539 unsigned long order; 2540 for (order = 0; ((1UL << order) << PAGE_SHIFT) < size; order++) 2541 ; 2542 table = (void*) __get_free_pages(GFP_ATOMIC, order); 2543 } 2544 } while (!table && size > PAGE_SIZE && --log2qty); 2545 2546 if (!table) 2547 panic("Failed to allocate %s hash table\n", tablename); 2548 2549 printk("%s hash table entries: %d (order: %d, %lu bytes)\n", 2550 tablename, 2551 (1U << log2qty), 2552 long_log2(size) - PAGE_SHIFT, 2553 size); 2554 2555 if (_hash_shift) 2556 *_hash_shift = log2qty; 2557 if (_hash_mask) 2558 *_hash_mask = (1 << log2qty) - 1; 2559 2560 return table; 2561} 2562